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?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.
answered Feb 17, 2018 at 17:47
-
$\begingroup$ Ahh I see that makes sense. Is there a proof for this somewhere or more where I can read? $\endgroup$ Feb 17, 2018 at 18:02
-
$\begingroup$ Note sure there's much more to say. Wikipedia says that Hopcroft and Tarjan described this as "well known" in the early 1970s. Any time your DFS completes without finding a cycle, you must have visited (and, hence, marked) all the vertices in the component you started in. So any unmarked vertex must be in a component you've not visited yet. $\endgroup$ Feb 17, 2018 at 21:09
$\begingroup$
$\endgroup$
2
Another option is to count the number of connected components using some graph traversal algorithm such as DFS or BFS, and compare it to the number of vertices and edges. If a graph has $n$ vertices, $m$ edges, and $c$ connected components, then it is acyclic iff $m = n - c$.
answered Feb 17, 2018 at 23:16