Answer to Question #265241 in Discrete Mathematics for Ishani Roy

Question

Which is the most suitable graph representation scheme for a dense graph? Draw its

representation with the help of an example. What is the space complexity of a such

graph representation scheme?

Answer 1

For a dense graph, O(e) = O(v2), and so adjacency matrices are the most suitable graph representation scheme for dense graphs, because in big-O terms they don't take up more space than storing all the edges in a linked list, and operations are much faster.