single algorithm to work on both directed and undirected graph to detect cycles?

Question

I have been trying to implement an algorithm to detect cycles (probably how many of them) in a directed and undirected graph. That is the code should apply for both directed and undirected graphs.

Using DFS or topological sort is mostly recommended in various posts. But largely, everything is addressed for undirected graph.

This link describes one approach for cycle detection. To my understanding this works for directed graphs.

This link has the code for cycle detection in undirected graphs. but I fail to understand how it ignores the back edge. That is it must ignore any cycles with two nodes, say D to C and C to D. which means it must remember it parent as the DFS recurses. But the code does not seem take care of that.

Any suggestions welcome..

enter image description here

Your second link is about detecting Connected Component, not about cycles. — justhalf
A cycle is a subgraph of k vertices where there are k edges connecting the k vertices into a single loop. Connected component is an induced subgraph of k vertices which is connected. In your graph example, there is only one connected component (the whole graph), and there are three cycles: A-B-E-A, A-B-D-A, A-E-B-D-A. — justhalf

Catalin Pol Catalin Pol · Accepted Answer · 2013-11-26T04:30:17

First, some important aspects: - detecting cycles is usually easier than counting them (since you can have cycles inside another cycle) - indeed, for directed and undirected graphs the algorithms can be very different (usually, a much more efficient one for the undirected case).

Second, my 2 cents for a general purpose algorithm (cycle counting for directed graph) would be a slightly modified Floyd-Warshall algorithm:

for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            A[i][j] += A[i][k] * A[k][j];
        }
    }
}

The above snippet assumes that A is the adjacency matrix of your graph and n is the number of nodes. Complexity is O(n^3) obviously.

It will modify the adjacency matrix to contain in each position (i,j) the number of paths starting from i and ending with j. In other words, if you are interested in the number of cycles that start with node x, just read A[x][x] (the corresponding number of the main diagonal of the matrix).

The only problem that remains here is if you are interested in a global cycle count. Since I don't have a proof of correctness for the solution I have in mind (and don't have the time to verify it), I won't post any details (sorry).

PS: For cycle detection (only), there are quicker options available:

in an undirected graph (easiest case), try looking into the Union find problem (Disjoint set data structure). This is one of the fastest non-trivial graph algorithms I know (almost linear with all optimizations in place if I remember correctly).
in a directed graph, I would use DFS as you mentioned. The second link you mentioned works fine if you put an else for the "if (!marked[v])" in the "dfs" function (as in: else 'a cycle was found').

single algorithm to work on both directed and undirected graph to detect cycles?

1 Answers