How to find which vertices are in a graph cycle

Question

eg. for 1->2, 2->3, 3->4, 4->2, I want to print 2, 3, 4. I tried DFS, and when I found vertex I visited before, I go to parent until I don't get this vertex, but it does not work well. Sometimes it enters an infinite loop.

Run dfs:

int i;
for (i = 0; i < MAX_VER; i += 1)
    if (ver[i].v == 0 && ver[i].nb > 0)
        dfs(i);

dfs:

ver[v].v = 1;

int i;
for (i = 0; i < ver[v].nb; i += 1) {
    ver[ver[v].to[i]].p = v;

    if (ver[ver[v].to[i]].v == 0)
        dfs(ver[v].to[i]);
    else
        // cycle found
        printCycle(ver[v].to[i]);
}

and print cycle:

printf("\cycle: %d ", v);

int p = ver[v].p;

while (p != v) {
    printf("%d(%d) ", p, v);

    p = ver[p].p;
}

printf("\n");

Vertex struct:

int *to; // neighbor list

int nb; // how many neighbor
int p; // parent
short v; // was visited? 0 = false, 1 = true

possible duplicate of [Best algorithm for detecting cycles in a directed graph](http://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph) — Steve, May 03 '12 at 09:02

score 1 · Answer 1 · edited May 23 '17 at 12:04

It sounds like you are looking for "Strongly Connected Components" - so you are in luck, there is a well known algorithm for finding these in a graph. See Tarjan.

The algorithm is pretty well described in that article, but it's a bit long winded so I won't paste it here. Also, unless you are doing this for study you will probably be better off using an existing implementation, it's not that hard to implement but it's not that easy either.

EDIT. It looks like this question is actually a dupe... it pains me to say this but it probably needs to be closed, sorry. See Best algorithm for detecting cycles in a directed graph

score 0 · Answer 2 · answered May 03 '12 at 10:02

0

You should use vertex coloring to avoid infinite loop in DFS. At first all vertices are marked as WHITE. When you discover a vertex at first time (it is marked as WHITE) you should mark it is as GREY. If you discovered a GREY vertex you would find a loop.

answered May 03 '12 at 10:02

Aligus

1,585
1
9
11

And how does this tell you which vertices are in the loop? – May 03 '12 at 13:41
You can use std::map or std::unordered_map to hold vertex type. – Aligus May 03 '12 at 14:51

How to find which vertices are in a graph cycle

2 Answers2