AlgoScope

Connected Components

Run BFS or DFS from every unvisited vertex. Each run colours one component.

Graph traversal, algorithm, beginner
Vertex 0 starts component 1.011234567u
Vertex 0 starts component 1.011234567u

BFS and DFS: Three components

Decision, step 2 of 13

Vertex 0 has no component number yet, so it starts component 1. Traverse from it.

How bfs and dfs works

Cost

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)

Leads to

Topics that need this one first.

Taught by the same lesson

BFS and DFS covers these too, in the same run.