图的深度优先遍历和广度优先遍历代码实现
深度优先遍历
定义：深度优先遍历类似于数的先序遍历，是树的先序遍历的推广。
- 从图中某个顶点v出发，访问v。
- 找到刚访问过得顶点的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复此步骤，直至刚访问的顶点没有未被访问的邻接点为止。
- 返回前一个访问过得且扔有未被访问的邻接点的顶点，找到该顶点的下一个未被访问的邻接点，访问该顶点。
- 重复步骤2，3，直至图中所有顶点都被访问过
广度优先遍历
定义：图的广度优先遍历就类似于树的层序遍历。
- 从图中某个顶点v出发，访问v。
- 依次访问v的各个未被访问过得邻接点。
- 分别从这些邻接点出发依次访问他们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。重复步骤3，直至图中所有已被访问的顶点的邻接点都被访问到。
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
| #include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
using namespace std;
typedef char TypeData; /* 数据类型 */
#define MAXVEX 100 /* 最大顶点数 */
#define INFINITY 65535 /* 用65535代表 正无穷 */
/* 存储采用邻接矩阵 */
typedef struct stGraph
{
TypeData vexs[MAXVEX]; /* 定点表 */
int arc[MAXVEX][MAXVEX]; /* 邻接矩阵，可看作边表 */
int numVertexes, numEdges;/* 图中当前的顶点数和边数 */
}MGraph;
/* 建立无向网图邻接矩阵表示 */
void createMGraph(MGraph* G);
/* 邻接矩阵的深度优先递归算法，针对每一个定点进行深度优先遍历 */
void DFS(MGraph* G, int i);
void DFSTraverse(MGraph* G);
/* 邻接矩阵的广度优先遍历 */
void BFSTraverse(MGraph* G);
/* 建立无向网图邻接矩阵表示 */
void createMGraph(MGraph* G)
{
int i = 0, j = 0, k = 0, w = 0;
cout << "请输入定点数和边数: ";
cin >> G->numVertexes >> G->numEdges;
/* 读入定点信息，建立定点表 */
cout << "请输入图的节点" << endl;
for(i = 0; i < G->numVertexes; i++)
{
cin >> G->vexs[i];
}
/* 初始化邻接矩阵 */
for(i = 0; i < G->numVertexes; i++)
{
for(j = 0; j < G->numVertexes; j++)
{
G->arc[i][j] = INFINITY;
}
}
/* 读入numEdges边信息 */
for(k = 0; k < G->numEdges; k++)
{
cout << "输入边(vi,vj)上的下标，i,j和权值w" << endl;
cin >> i >> j >> w;
G->arc[i][j] = w;
/* 因为是无向图，矩阵对称 */
G->arc[j][i] = w;
}
}
/* 邻接矩阵的深度优先遍历和广度优先遍历所用辅助数组
记录图中的节点是否被访问过 */
int visited[MAXVEX] = {0};
/* 邻接矩阵的深度优先递归算法，针对每一个定点进行深度优先遍历 */
void DFS(MGraph* G, int i)
{
int j = 0;
visited[i] = 1;
/* 打印定点的信息 */
cout << G->vexs[i] << " ";
for(j = 0; j < G->numVertexes; j++)
{
if(G->arc[i][j] != 65535 && visited[j] == 0 )
{
DFS(G,j);
}
}
}
void DFSTraverse(MGraph* G)
{
int i = 0;
/* 把每一个定点都设为未访问过 */
for(i = 0; i < G->numVertexes; i++)
{
visited[i] = 0;
}
/* 对未访问过的定点调用DFS */
for(i = 0; i < G->numVertexes; i++)
{
if(visited[i] == 0)
{
DFS(G,i);
}
}
}
/* 邻接矩阵的广度优先遍历 */
void BFSTraverse(MGraph* G)
{
int i = 0, j = 0;
queue<int> myqueue;
/* 初始化，把每一个定点都设为未访问过 */
for(i = 0; i < G->numVertexes; i++)
{
visited[i] = 0;
}
/* 对每一个定点做循环 */
for(i = 0; i < G->numVertexes; i++)
{
/* 如果节点没有被访问过 */
if(visited[i] == 0)
{
/* 该节点设置为已经被访问 */
visited[i] = 1;
/* 打印出该节点,并把该节点入队列 */
cout << G->vexs[i] << " ";
myqueue.push(i);
/* 若当前的队列不为空 */
while(!myqueue.empty())
{
i = myqueue.front();
myqueue.pop();
for(j = 0; j < G->numVertexes; j++)
{
/* 判断其他定点若与当前的定点存在边且未访问过 */
if(G->arc[i][j] != 65536 && visited[j] == 0)
{
visited[j] = 1;
cout << G->vexs[j] << " ";
myqueue.push(j);
}
}
}
}
}
}
int main(void)
{
MGraph* pGraph = new MGraph;
int i = 0, j = 0;
/* 创建一个图 */
createMGraph(pGraph);
/* 深度优先遍历 */
// DFSTraverse(pGraph);
/* 广度优先遍历 */
BFSTraverse(pGraph);
delete pGraph;
return 0;
}
|
