判斷一個圖中有無環路的存在

這里要引入兩個概念：

1.樹邊：是一條未被遍歷過的邊，它指向一個未被訪問過的點。

2.反向邊：是一條未被遍歷過的邊，它指向一個被訪問過的點。

如果圖中有環路的存在，那么環路的最后一個邊必然是一條反向邊。

?

那么，我們在DFS遍歷的過程當中，只需要添加一條語句來判斷所有未被檢查過的邊的指向點是否已被訪問過，就可以判斷出這個圖是否存在環路了。

?

#include <stdio.h>
#include <string.h>const int maxv = 1000;
const int maxe = 5000;
const int maxn = 1000;
/*
* 鄰接矩陣
*
*/
struct adjMetrix {int G[maxn+10][maxn+10];int visit[maxn];int n;void addedge(int u, int v) {G[u][v] = 1;return ;}void read() {memset(G, 0, sizeof(G));memset(visit, 0, sizeof(visit));int u, v, w;scanf("%d", &n);for (int i=0; i<n; i++) {scanf("%d %d", &u, &v);addedge(u, v);}return ;}void dfs(int i) {for (int j=0; j<=n; j++) {if (G[i][j]!=0 && visit[j]==0) {printf("%d %d\n", i, j);visit[j] = 1;dfs(j);}}}
};/*
* 鄰接鏈表
*
*/
struct Edge {int to, w, next;
};struct adjTable {int node[maxv];int visit[maxe];int cnt;bool cycle;struct Edge e[maxe];void init() {memset(node, -1, sizeof(node));memset(visit, 0, sizeof(visit));cnt = 0;cycle = false;}void addedge(int u,int v) {e[cnt].to = v;e[cnt].next = node[u];node[u] = cnt++;}void read() {int n, u, v, w;scanf("%d", &n);for (int i=1; i<=n; i++) {scanf("%d %d", &u, &v);addedge(u, v);}return ;}void dfs(int p) {int i;for (i=node[p]; i!=-1; i=e[i].next) {if ( visit[e[i].to] )cycle = true;if (visit[ e[i].to ] == 0) {printf("%d %d\n", p, e[i].to);visit[ p ] = 1;dfs( e[i].to );}}}
};struct adjTable table;int main() {freopen("in.txt", "r", stdin);table.init();table.read();table.dfs(1);if (table.cycle)printf("有環！\n");elseprintf("無環！\n");return 0;
}

?

　　

?