CODEWITHSUNDEEP
algorithmgraphgraph-algorithm
user1242199
user1242199

Reputation:

How to find which vertices are in a graph cycle

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

Upvotes: 1

Views: 1777

Answers (2)

Aligus
Aligus

Reputation: 1605

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.

Upvotes: 0

Steve
Steve

Reputation: 8511

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

Upvotes: 1

Related Questions