Find a circuit in a direct graph

Question

I want to find a circuit in a direct graph , this circuit starts at a specific vertex and ends at it. I use adjacency list data structure to create this graph but I could n't know how the algorithm would be, please help me. Thanks a lot

Did you try [Googling it](http://www.google.com/#hl=en&output=search&sclient=psy-ab&q=detect+cycles+in+directed+graph&oq=detect+cycles+in+dir&aq=0&aqi=g1g-q2&aql=&gs_l=hp.3.0.0j0i22l2.5304.10257.0.11144.20.12.0.8.8.0.208.1915.0j11j1.12.0...0.0.-eh4kSQJRfQ&pbx=1&bav=on.2,or.r_gc.r_pw.r_qf.,cf.osb&fp=d0f8cd49a0fc8cd2&biw=1138&bih=555)? — Chris Eberle, May 05 '12 at 00:47
You can use Tarjan's algorithm. See http://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph — spinlok, May 05 '12 at 00:47
Thanks for all , I get the point and I'll try and post my atemption — Princess Rana, May 05 '12 at 04:49

score 1 · Accepted Answer · answered May 05 '12 at 00:50

1

May be this hint will help:

traverse graph (any algo - BFS DFS)
Color node which you've visited AND Store its parent
check if the node you're traversing is already colored, then loop back to its parents until you get same node.

answered May 05 '12 at 00:50

code muncher

1,592
2
27
46

score 0 · Answer 2 · answered May 05 '12 at 00:50

0

DFS would find a cycle.

http://en.wikipedia.org/wiki/Cycle_%28graph_theory%29

answered May 05 '12 at 00:50

DarthVader

52,984
76
209
300

Thanks for all. I get the point and I'll try and post my attempt soon – Princess Rana May 05 '12 at 04:46

score 0 · Answer 3 · answered May 05 '12 at 11:43

0

void DFS (Node* ptr , int node , int index , int n )

{ int i;

if ( ptr == NULL)
{
    ptr=arrNode[index].next;
    node = ptr->vertex;
}

for ( int i=0 ; i < n ; i++)
{
    if ( ( node == arrNode[i].vertex) && (ptr->visit=false))
    {
        ptr=arrNode[i].next;
        ptr->visit = true;
        s.push(arrNode[i].vertex);
    }
    ptr=ptr->next;
    DFS(ptr,ptr->vertex,i+1 , n );

}

}

answered May 05 '12 at 11:43

Princess Rana

9
2

I have written this code , there is something wrong I can't get it. My data structure is an array its length = vertex number , each field of this array has a pointer to linked list which contains all its neighbors :( – Princess Rana May 05 '12 at 11:46
This would probably be better edited into your question, so that readers can see your current work. I am sure once you do so, you will get more positive responses - best of luck `:)` – halfer May 05 '12 at 12:05

Find a circuit in a direct graph

3 Answers3