Detect Cycle in a Directed Graph

Reference:

1. GeeksforGeeks: Detect Cycle in a Directed Graph

在有向性的圖形內找出有無迴圈

下面的例子,是從2這個點開始

所以會找出

1->2
0->2
3->3

是造成迴圈的邊

Graph:

           0 -------→ 1
          ↓ ↑       ↙    
          ↓ ↑     ↙
          ↓ ↑   ↙
          ↓ ↑ ↙
  start--->2 -------→ 3 →
                      ↑   ↓
                        ← 

#define GRAPH_MAX 4

bool graph[GRAPH_MAX][GRAPH_MAX] = {{0,1,1,0},            
                                    {0,0,1,0},
                                    {1,0,0,1},
                                    {0,0,0,1}};

bool    bVisited[GRAPH_MAX]     = {false};

void DFS(int v)
{
    int i;
    bVisited[v] = true;

    for(i=0; i<GRAPH_MAX; i++) {
        if(graph[v][i] && !bVisited[i]) {
            DFS(i);
        }
        else if(graph[v][i] && bVisited[i])
            printf("(%d,%d)\n", v, i);
    }
}

int main(int argc, char* argv[])
{
    DFS(2);     

    return 0;
}

output:

(1,2)
(0,2)
(3,3)