Graph Theory37 sections · 1633 units
Open in Course

SCC in Undirected Graphs?

(Why it doesn't apply)

SCCs only make sense for directed graphs where edges have direction. In an undirected graph, if you can reach node vv from node uu, you can always reach uu from vv by reversing the path. Every connected component in an undirected graph is trivially "strongly connected".

For undirected graphs, use simple DFS or BFS to find connected components in O(V+E)O(V + E) time. No need for SCC algorithms like Kosaraju or Tarjan.

Space complexity is O(V)O(V) for the data structures used.