警告
本文最后更新于 2023-07-07，文中内容可能已过时。
广度优先搜索（BFS）
广度优先搜索在进一步遍历图中顶点之前，先访问当前顶点的所有邻接结点。访问了就入队。
深度优先搜索（DFS）
深度优先搜索在搜索过程中访问某个顶点后，需要递归地访问此顶点的所有未访问过的相邻顶点。
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
| #include <bits/stdc++.h>
#define N 5
using namespace std;
int maze[N][N] = {//无权有向图邻接矩阵
{ 0, 1, 0, 1, 0 },
{ 0, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 1 },
{ 0, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 0 }
};
int visited[N];
void DFS(int start)
{
cout << start<< " ";
visited[start] = 1;
for (int i = 0; i < N; i++)
{
if (!visited[i] && maze[start][i] == 1)//没访问过且为邻居节点
DFS(i);
}
}
void BFS(int start){
queue<int> Q;//队列
Q.push(start);
visited[start] = 1;
while (!Q.empty())
{
int front = Q.front();//头
cout << front << " ";
Q.pop();
for (int i = 0; i <N; i++)
{
if (!visited[i] && maze[front][i] == 1)
{
visited[i] = 1;
Q.push(i);
}
}
}
}
int main()
{
memset(visited,0,sizeof(visited));
for (int i = 0; i < N; i++)//不连通的情况
{
if (visited[i] == 1)//访问过
continue;
DFS(i);
}
cout<<endl;
memset(visited,0,sizeof(visited));
for (int i = 0; i < N; i++)//不连通的情况
{
if (visited[i] == 1)//访问过
continue;
BFS(i);
}
return 0;
}
|
传送门
Jian YE
支付宝
微信