How can I design an algorithm using BFS(Breadth First Search) or DFS(Depth First Search) algorithms in order to determine the connected components of a non-connected graph? The algorithm must be able to denote the set of vertices of each connected component.
This is my approach:
Run DFS starting from each node:
Start by labeling all nodes as unvisited. Then, iterate over the nodes in any order. For each node, if it's not already labeled as being in a connected component, run DFS from that node and mark all reachable nodes as being in the same CC. If the node was already marked, skip it. This then discovers all CC's of the graph one CC at a time.
Moreover, this is very efficient. If there are m edges and n nodes, the runtime is O(n) for the first step (marking all nodes as unvisited) and O(m + n) for the second, since each node and edge are visited at most twice. Thus the overall runtime is O(m + n).
Any idea of how to improve this solution?.