深度优先遍历之树边，前向边，回边，横跨边

无意翻到一篇大佬的博客，感觉写得很好，给了我很大的帮助，特此转发。

转自：http://blog.csdn.net/wshish920907/article/details/73276813

根据在有向图G上进行深度优先遍历所产生的深度优先森林，可以把图中的边分为四类：

（1）树边：是DFS森林的实际组成部分。如果顶点v是在探测边（u，v）时首次被发现的，那么（u，v）就是一条树边。

（2）前向边：：是DFS树中从一个顶点指向该顶点的一个非子顶点后裔的边。

（3）回边：是DFS树中从一个顶点指向其祖先的边（有向图中可能出现的自环也被认为是反向边）。

（4）横跨边：既不是从一个顶点指向其后裔的边，也不是指向其祖先的边边；横跨边是从一个顶点指向一个已完全访问过的顶点的边（即就是已经在该顶点上进行了postvisit操作的边）。

对于每条边（u， v），当第一次探测时，geneva所到达的顶点v的颜色和时间戳来判断：

（1）（colour[v] == -1）表示它是一条树边。

（2）（colour[v] == 0）表示它是一条回边。

（3）（colour[v] == 1）&&（d[u] < d[v]）表示它是一条前向边。

（4）（colour[v] == 1）&&（d[u] > d[v]）表示它是一条横跨边。

如图：实线表示树边，点线表示回边，虚线表示前向边，弯线表示横跨边。

具体实现代码如下：

 1 #include<iostream>
 2 #include<vector>
 3 #include<fstream>
 4 using namespace std;
 5 
 6 void DFS_Visit(int v);
 7 
 8 int nodeNum;//图中顶点数
 9 int edgeNum;//图中边数
10 vector< vector<int> > mGraph;//图的存储结构
11 int *colour;//初始化是-1，被探测是0,探测结束为1
12 int *d;//开始时间
13 int *f;//结束时间
14 int t = 0;//时间从零开始
15 
16 
17 //深度优先搜索
18 void DFS()
19 {
20     for(int i = 0; i < nodeNum; ++i)
21     {
22         colour[i] = -1;
23     }
24 
25     for(int i = 0; i < nodeNum; ++i)
26     {
27         if(colour[i] == -1)
28         {
29             DFS_Visit(i);
30         }
31     }
32 }
33 
34 //从节点v开始深度优先搜索
35 void DFS_Visit(int v)
36 {
37     colour[v] = 0;
38     d[v] = ++t;//记录开始时间
39     int count = mGraph[v].size();
40     for(int i = 0; i < count; ++i)
41     {
42         int val = mGraph[v][i];
43         if(colour[val] == -1)
44         {
45             cout<<"("<<v<<", "<<val<<")树边"<<endl;
46             DFS_Visit(val);
47         }
48         else if(colour[val] == 0)
49         {
50             cout<<"("<<v<<", "<<val<<")后向边"<<endl;
51         }
52         else
53         {
54             if(d[v] < d[val])//前向边
55             {
56                 cout<<"("<<v<<", "<<val<<")前向边"<<endl;
57             }
58             else if(d[v] > d[val])//后向边
59             {
60                 cout<<"("<<v<<", "<<val<<")交叉边"<<endl;
61             }
62         }
63     }
64     f[v] = ++t;//记录结束时间
65     colour[v] = 1;
66 }
67 
68 int main()
69 {
70     cout << "Please input nodeNum" << endl;
71     cin >> nodeNum;
72     cout << "Please input edgeNum" << endl;
73     cin >> edgeNum;
74     mGraph.resize(nodeNum);
75     colour = new int[nodeNum];
76     d = new int[nodeNum]();
77     f = new int[nodeNum]();
78     cout << "Please input edge" << endl;
79     int num1, num2;
80     for(int i = 0; i < edgeNum; ++i)
81     {
82         cin >> num1 >> num2;
83         mGraph[num1].push_back(num2);
84     }
85     DFS();
86     for (int i = 0; i < nodeNum; i ++){
87         cout << d[i] << " ";
88     }
89     cout << endl;
90     for (int i = 0; i < nodeNum; i ++){
91         cout << f[i] << " ";
92     }
93     return 0;
94 }

实现结果如下：