Why does the time complexity of DFS and BFS depend on the way the graph is represented?

data-structures graph time-complexity graph-algorithm breadth-first-search
Nitish Jain picture Nitish Jain · May 29, 2014 · Viewed 20.3k times · Source

The site http://web.eecs.utk.edu/~huangj/CS302S04/notes/graph-searching.html describes that when an adjacency list is used then, DFS and BFS have complexity O(V+E), and if an adjacency matrix is used, the complexity is O(V2). Why is this?

Answer

templatetypedef picture templatetypedef · May 29, 2014

In both cases, the runtime depends on how long it takes to iterate across the outgoing edges of a given node. With an adjacency list, the runtime is directly proportional to the number of outgoing edges. Since each node is visited once, the cost is the number of nodes plus the number of edges, which is O(m + n). With am adjacency matrix, the time required to find all outgoing edges is O(n) because all n columns in the row for a node must be inspected. Summing up across all n nodes, this works out to O(n2).

Hope this helps!

Related questions

Explanation of runtimes of BFS and DFS

Why are the running times of BFS and DFS O(V+E), especially when there is a node that has a directed edge to a node that can be reached from the vertex, like in this example in the following …

Read More
Representing graphs (data structure) in Python

How can one neatly represent a graph in Python? (Starting from scratch i.e. no libraries!)What data structure (e.g. dicts/tuples/dict(tuples)) will be fast but also memory efficient?One must be able to do various graph …

Read More
What exactly is augmenting path?

When talking about computing network flows, the Algorithm Design Manual says: Traditional network flow algorithms are based on the idea of augmenting paths, and repeatedly finding a path of positive capacity from s to t and adding it to the …

Read More