GR1: Strongly Connected Components

Question 1

Runtime of DFS

Answer 1

O(|V| + |E|)

Question 2

Runtime of BFS

Answer 2

O(|V| + |E|)

Question 3

Runtime of Topological Sort

Answer 3

Just one pass of DFS to get post order numbers (O(|V| + |E|)), then one pass through an array, inserting vertices so they are ordered by post order number (O(|V|)).

O(|V| + |E|) overall.

Question 4

Runtime of SCC

Answer 4

Two passes of DFS, so O(|V| + |E|)

Question 5

Runtime of Kruskal’s

Answer 5

O(|E| log |V|)

Question 6

Runtime of Dijkstra’s

Answer 6

We assume the binary min-heap implementation. Dijkstra uses the BFS framework, which is O(|V| + |E|), but each min-heap operation is O(log |V|), so overall Dijkstra’s is O((|V| + |E|) log |V|).

Question 7

Runtime of Prim’s

Answer 7

Prim is nearly identical to Dijkstra except that it uses a different key value for its min-heap. This makes it O((m + n)log n) just like Dijkstra.