Answer to Question #271984 in Algorithms for Anu

Question

(i) 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?

(ii) How does DFS graph traversal scheme work? Explain.

Answer 1

i)

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.