无向图中寻找桥

 1 /*==================================================*\
 2  |  无向图找桥
 3  | INIT: edge[][]邻接矩阵;vis[],pre[],anc[],bridge 置0;
 4  | CALL: dfs(0, -1, 1, n);
 5  \*==================================================*/
 6 int bridge, edge[V][V], anc[V], pre[V], vis[V];
 7 //vis[i]   0--尚未访问   1--正在访问   2--已经访问结束
 8 //anc[i]   该点能到达的最小序号
 9 //pre[i]   该点的序号
10 void dfs(int cur, int father, int dep, int n) { // vertex: 0 ~ n-1
11     if (bridge)//已经找到桥了
12         return;
13     vis[cur] = 1;//正在访问
14     pre[cur] = anc[cur] = dep;
15     for (int i = 0; i < n; ++i)
16         if (edge[cur][i]) {//有一条边cur-->i
17             if (i != father && 1 == vis[i]) {
18                 if (pre[i] < anc[cur])
19                     anc[cur] = pre[i]; //这是一条回边
20             }
21             if (0 == vis[i]) { //这是一条树边
22                 dfs(i, cur, dep + 1, n);
23                 if (bridge)
24                     return;
25                 if (anc[i] < anc[cur])
26                     anc[cur] = anc[i];//更新该点能到达的最小值
27                 if (anc[i] > pre[cur]) {
28                     bridge = 1;
29                     cout<<cur<<"  "<<i<<endl;
30                     return;
31                 }
32             }
33         }
34     vis[cur] = 2;
35 }
如果想找到所有的桥，即把bridge的标记相关的代码去掉即可。