深搜广搜

Lruihao 收录于 ACM

2018-07-22 2023-11-17 约 500 字预计阅读 1 分钟 - 次阅读

注意

本文最后更新于 2023-11-17，文中内容可能已过时。

0.1 广度优先搜索（BFS）

广度优先搜索在进一步遍历图中顶点之前，先访问当前顶点的所有邻接结点。访问了就入队。

0.2 深度优先搜索（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;
 }

传送门

0.1 广度优先搜索（BFS）

0.2 深度优先搜索（DFS）

相关内容