超简单的BFS广度优先搜索代码

1
#include<iostream>

1
2
#include<queue>

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
//广度优先搜索测试
//例：
//
1
//
/ | 
//
/
|

//
2
3---5
//
|
//
|
//
4
//step1:将存储图的方法称为图的*邻接矩阵存储法*
// 通路用1表示，不通用-1表示，自身为0
//
1
2
3
4
5
// 1
0
1
1
-1
1
// 2
1
0
-1
1
-1
// 3
1
-1
0
-1
1
// 4
-1
1
-1
0
-1
// 5
-1
-1
1
-1
0
// step2:构造二维表
const int NUM = 100;
int road[NUM][NUM];
//记录通路
bool book[NUM];
//记录是否已经被访问
void BounTable(int n)
//初始化
{
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
road[i][j] = (i == j) ?
0 : -1;
}
void RoadSet()
//路径设置
{
road[1][2] = road[2][1] = 1;
road[1][3] = road[3][1] = 1;
road[2][4] = road[4][2] = 1;
road[3][5] = road[5][3] = 1;
road[1][5] = road[5][1] = 1;
}
void BookSet(int n)
//未访问的节点设置为true，为了防止重复访问
{
for(int i = 1; i <= n; i++)
book[i] = true;
}
//广度优先搜索
void bfsTest()
{
int n = 5, sum = 0;
//v当前节点编号；sum累计访问节点个数；n节点总个数
BounTable(n);
RoadSet();
BookSet(n);
queue<int> Pt;
Pt.push(1); book[1] = false;
while(!Pt.empty())
{
int v = Pt.front();
//访问的当前节点序号
cout << v << " ";
Pt.pop();
for(int i = 1; i <= n; i++)
{
if(road[v][i] == 1 && book[i])
{
Pt.push(i);
book[i] = false;    //访问后的设为false
}
}
}
}