algorithmscomputer sciencegraph theory
I want to know if a directed graph has a cycle; something like
1->2->3->2 ...
1->2->3->4->3...
1->1->1->1...
So, I'm considering the Tarjan's strongly connected algorithm.
Do you think that with this algorithm I'll be able to know if some directed graph has a cycle?
Thanks!
A loop is commonly defined as an edge (or directed edge in the case of a digraph) with both ends as the same vertex. (For example from $a$ to itself). Although loops are cycles, not all cycles are loops. In fact, none of the above digraphs have any loops.
Cycles are usually defined as closed walks which do not repeat edges or vertices except for the starting and ending vertex. This definition usually allows for cycles of length one (loops) and cycles of length two (parallel edges).
Note that cycles (and walks) do not make any reference to the orientation of the edges in question. Directed cycles (and directed walks) may only travel along the "forward" direction of the edges. In particular, that implies that $G_3$ pictured above has a third cycle, $(\color{blue}{(a,b)},(b,c),(c,a))$ where the $\color{blue}{(a,b)}$ refers instead to the edge pointing from $b$ to $a$.
Technically, all of the graphs above except for $G_2$ are directed multigraphs since in each you have parallel edges. Although in simple graphs (graphs with no loops or parallel edges) all cycles will have length at least $3$, a cycle in a multigraph can be of shorter length. Usually in multigraphs, we prefer to give edges specific labels so we may refer to them without ambiguity.
As for being strongly connected, yes all of them are and your definition is correct.
Your additional question, "what is the difference between a cycle and a connected component"
The above graph contains a cycle (though not a directed cycle) yet is not strongly connected.
One can prove that if a directed multigraph is strongly connected then it contains a cycle (take a directed walk from a vertex $v$ to $u$, then a directed walk from $u$ to $v$. Any closed walk contains a cycle).
One can also show that if you have a directed cycle, it will be a part of a strongly connected component (though it will not necessarily be the whole component, nor will the entire graph necessarily be strongly connected).
I've come to a solution somewhat simpler.
Let D be a strongly connected digraph. Let $C = v_1 v_2 ... v_m$, $v_m = v_1$, be an odd cycle in the underlying graph. For each i, from 1 to m-1, let $W_i$ be a minimal walk from $v_i$ to $v_{i+1}$. If both vertices are connected by an edge $e_i = v_iv_{i+1}$, then $W_i = v_ie_iv_{i+1}$. Else, if the edge is $v_{i+1}v_i$, then suppose $W_i$ is an odd length walk (otherwise, we'd have an odd length cycle and be done by now). Since m-1 is odd, we have constructed an odd number of odd length walks. Concatenating them as $W_0 . W_1 . ... W_{m-1}$, we have a closed odd walk. Since every closed odd walk has a closed odd cycle, we're done.
Best Answer
Tarjan's algorithm may be used to detect cycles in a directed graph as follows: When the root node of a (maximal) strongly connected component (SCC) is detected, the nodes in the SCC are popped from the stack. At that point, if more than one node is popped, then it is known that the graph contains a cycle. If the SCC contains a single node, one has to check whether that node has a "self-loop" (which gives a cycle) or not (that is, the node makes up a trivial SCC).
Said otherwise, if the directed graph has no cycles, Tarjan's algorithm will only find SCCs consisting of individual nodes without self-loops.
If the cycle needs to be identified and the SCC found has more than one node, one can perform a depth-first search from the SCC root, limited to the nodes that are in that SCC and until the root of the SCC is re-entered.
In fact, in practice, cycle detection in directed graphs is performed by two nested depth-first searches, without concern for the enumeration of SCCs, especially when cycles have to go through some designated nodes.
When the "outer" DFS is about to retreat from a (designated) node $v$, a second DFS is run from $v$ to see if some node $u$ currently on the stack of the outer DFS may be reached from $v$.
If that is the case, we have a cycle reachable from the node from which the first DFS started. Such a cycle goes through both $v$, the node from which the outer DFS is about to retreat, and $u$, the node on the stack of the outer DFS found during the inner DFS. We know we can reach $v$ from $u$ because $u$ is on the stack of the outer DFS. We know we can reach $u$ from $v$ because the inner DFS says so.
The nested DFS algorithm is not asymptotically faster than Tarjan's algorithm, but often performs better.