数据结构——深度优先遍历（DFS）无向非连通图

以下是数据结构中关于深度优先遍历非无向连通图的操作（编程风格参考严蔚敏版数据结构）。
其实深度优先遍历就是二叉树的先序遍历的推广。

和连通图DFS核心代码的小小差异：

void DFS(AMGraph &G,VerTexType v){//节点v 
	int vi = LocateVex(G,v);//vi(v-index)的下标 
	cout<<G.vexs[vi]<<" ";//输出当前节点
	visited[vi] = true;//已访问 
	for(int vn=FirstAdjVex(G,v);vn>=0;vn=NextAdjVex(G,v,vn)){//vn(v-next)表示v的全部邻接点的下标（如果vn<0表示不存在邻接点） 
		if(!visited[vn]){//当前邻接点未被访问过 
			VerTexType V = Transform(G,vn);//将该下标转回节点名称进行迭代 
			DFS(G,V);
		} 
	} 
} 

void DFSTraverse(AMGraph &G){
	for(int i=0;i<G.vexnum;i++){
		if(!visited[i]){//当前邻接点未被访问过 
			VerTexType V = Transform(G,i);//将该下标转回节点名称进行迭代 
			DFS(G,V);
		}
	}
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

没错，在原本连通图的DFS代码前，多了一层遍历，这就是非连通图的DFS算法。、
为什么要多一层嵌套呢？
我们看一个例子：

我们将原本的连通图截断，变成了三部分。
如果像连通图那样子用DFS，就会导致不管从哪个节点出发，都只能在自己所在的子图里遍历，而无法做到遍历完整的图。此时循环的作用就是：尝试遍历每一个节点，不放过每一个节点就可以把每一个子图以深度优先遍历的方式给遍历完成了（就是尝试从每个节点开始访问）。

运行结果

执行过程：
第一个DFS大循环：从A开始，访问A（输出A）：找到第一个未被访问的邻接点B，访问B；
访问B（输出B），找到B的第一个未被访问过的邻接节点D，访问D；
访问D（输出D），D的全部邻接节点全被访问过了（DFS里的小循环for(int vn=FirstAdjVex(G,v);vn>=0;vn=NextAdjVex(G,v,vn))做的就是这件事），第一个DFS结束。
第二个大循环开始：尝试从B开始访问，但是B也被访问过了，跳过。C没被访问，从C开始访问：
访问C（输出C），找到C第一个未被访问过的节点F，访问F；
访问F（输出F），找到F第一个未被访问过的节点G，访问G；
访问G（输出G），G的全部邻接节点全被访问过了，第二次DFS大循环结束。
第三个大循环开始：尝试从D开始访问，但D被访问过了，E没访问过，访问E。
访问E（输出E），找到E的第一个未被访问的邻接节点H，访问H；
访问H（输出H），H的全部邻接节点都被访问过了，第三个大循环结束。
往后的循环就是尝试从E、F、G、H开始访问，但是全部都访问过了，全部跳过。程序结束。

关于其他子函数，详情移步数据结构——深度优先遍历（DFS）无向连通图查看。

源代码：

#include
#include
using namespace std; 
typedef char VerTexType; //代表节点变量的类型（一般我们用ABCD表示节点，所以用char）
typedef int ArcType; //  代表边变量的类型（肯定用长度表示边呀，所以用int或者double都可）
#define MaxInt 32767 //边的最大值（表示目标不可达）
#define MVNum 100    //最大节点数 
#define OK 1
#define ERROR -1;
typedef int status;
bool visited[MVNum];//标记访问记录的数组；宏定义会自动赋值为0 
typedef struct{
	VerTexType vexs[MVNum] {'A','B','C','D','E','F','G','H'};//节点表
	ArcType arcs[MVNum][MVNum];//邻接表（肯定是个正方形的矩阵）
	int vexnum = 8,arcnum = 9;//该邻接矩阵的节点数、边数  
}AMGraph; 

int LocateVex(AMGraph G, VerTexType v){
	int i;
	for(i=0;i<G.vexnum;i++){
		if(G.vexs[i]==v){
			return i;
		}
	} 
	return ERROR;
}

status CreateUDN(AMGraph &G){//创建无向图 	
	for(int i=0;i<G.vexnum;i++){
		for(int j=0;j<G.vexnum;j++){
			if(i==j){
				G.arcs[i][j] = 0;
			}else
				G.arcs[i][j] = MaxInt;//初始状态全部节点之间相互不可达
		}
	}
	G.arcs[0][1]=1;
	G.arcs[1][3]=1;
	G.arcs[2][5]=1;
	G.arcs[2][6]=1;
	G.arcs[4][7]=1;
	G.arcs[5][6]=1;
	for(int i=0;i<G.vexnum;i++){
		for(int j=i+1;j<G.vexnum;j++){
			if(G.arcs[i][j]==1){
				G.arcs[j][i] = 1;
			} 
		}
	}//矩阵对称 
	return OK; 
}

void ShowGraph(AMGraph G){
	cout<<" ";
	for(int i=0;i<G.vexnum;i++){
		cout<<" "<<G.vexs[i];
	}
	cout<<endl;
	for(int i=0;i<G.vexnum;i++){
		cout<<G.vexs[i]<<" ";
		for(int j=0;j<G.vexnum;j++){
			if(G.arcs[i][j]==MaxInt){
				cout<<"* ";
			}else{
				cout<<G.arcs[i][j]<<" ";
			}
				
		}
		cout<<endl;
	}
}

VerTexType Transform(AMGraph G, int vn){
	return G.vexs[vn]; 
}

int FirstAdjVex(AMGraph G,VerTexType v){//v的第一个邻接点 
	int vi = LocateVex(G,v);
	for(int i=0;i<G.vexnum;i++){
		if(!visited[i]&&G.arcs[vi][i]==1){
			return i;//找到邻接点且此邻接点未被访问过 
		}
	} 
	return ERROR;//未找到邻接点 
}

int NextAdjVex(AMGraph G,VerTexType v ,int vn){//v相对于vn的下一个邻接点 
	int vi = LocateVex(G,v);
	
	for(int i=vn+1;i<G.vexnum;i++){
		if(!visited[i]&&G.arcs[vi][i]==1){
			return i;//找到邻接点且此邻接点未被访问过 
		}
	} 
	return ERROR;//未找到下一个邻接点 
}

void DFS(AMGraph &G,VerTexType v){//节点v 
	int vi = LocateVex(G,v);//vi(v-index)的下标 
	cout<<G.vexs[vi]<<" ";//输出当前节点
	visited[vi] = true;//已访问 
	for(int vn=FirstAdjVex(G,v);vn>=0;vn=NextAdjVex(G,v,vn)){//vn(v-next)表示v的全部邻接点的下标（如果vn<0表示不存在邻接点） 
//		cout<
		if(!visited[vn]){//当前邻接点未被访问过 
			VerTexType V = Transform(G,vn);//将该下标转回节点名称进行迭代 
			DFS(G,V);
		} 
	} 
} 

void DFSTraverse(AMGraph &G){
	for(int i=0;i<G.vexnum;i++){
		if(!visited[i]){//当前邻接点未被访问过 
			VerTexType V = Transform(G,i);//将该下标转回节点名称进行迭代 
			DFS(G,V);
		}
	}
	
} 

int main(){
	AMGraph G;
	CreateUDN(G);
	ShowGraph(G);
	DFSTraverse(G);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127