Depth First Search Algorithm implemented in C++.
- Perform a depth-first search of the graph. Your program should ask for the starting node.
- Compute the discovery and finish times of the nodes.
- Classify the edges (tree, back, ...) as early as possible instead of doing it after the DFS is fully done.
- Check if the graph has cycles. In the case of directed graphs, find a topological sort if one exists (i.e., if the graph is acyclic); in case the graph is acyclic, the program should compute a topological number for the nodes and should print the nodes in a topologically sorted order.
- If a directed graph has cycles, the program should find the strongly connected components and print the strongly connected components.
- In the case of undirected graphs, check if the graph is connected, and print each connected component.