Algorithm - Checking if an unconnected graph is cyclical I have an algorithm for finding if there is a cycle in a connected graph by depth first path creation of a graph until there is a duplicate in the path. Beside simply starting this algorithm at all possible points for an unconnected graph, how can I find if an unconnected graph is cyclical in good time and in a simple way?
As part of the cycle checking, you already need to keep track of which vertices have been visited. So just restart at the first unvisited vertex each time you exhaust a component.