深度优先搜索与广度优先搜索

1
#include <iostream>
2
#include <vector>
3
using namespace std;
4

5
/**
6
 * 深度优先搜索（递归实现）
7
 * @param node    当前访问的节点编号
8
 * @param graph   图的邻接表表示，graph[i] 存储节点 i 的所有邻居
9
 * @param visited 访问标记数组，visited[i] 为 true 表示节点 i 已访问
10
 */
11
void dfs(int node, const vector<vector<int>> &graph, vector<bool> &visited) {
12
    // 标记当前节点已访问，并输出
13
    visited[node] = true;
14
    cout << node << " ";
15

16
    // 遍历当前节点的所有邻居
17
    for (int neighbor : graph[node]) {
18
        // 如果邻居未被访问，则递归深入
19
        if (!visited[neighbor]) {
20
            dfs(neighbor, graph, visited);
21
        }
22
    }
23
}
24

25
int main() {
26
    int n = 7;  // 图中节点总数（节点编号 1~7）
27
    // 使用邻接表存储图，下标从 0 开始，多开一个位置方便直接按编号索引
28
    vector<vector<int>> graph(n + 1);
29

30
    // 根据示例图片构建无向图
31
    graph[1] = {2, 3, 4};
32
    graph[2] = {1, 6};
33
    graph[3] = {1, 7};
34
    graph[4] = {1};
35
    graph[5] = {6};
36
    graph[6] = {2, 5, 7};
37
    graph[7] = {3, 6};
38

39
    // visited[i] 标记节点 i 是否已被访问
40
    vector<bool> visited(n + 1, false);
41

42
    cout << "DFS 遍历顺序：";
43
    dfs(1, graph, visited);  // 从节点 1 开始 DFS
44
    cout << endl;
45

46
    return 0;
47
}

1
#include <iostream>
2
#include <vector>
3
#include <queue>
4
using namespace std;
5

6
/**
7
 * 广度优先搜索（队列实现，使用邻接矩阵存储图）
8
 * @param n     节点总数
9
 * @param start 搜索起点
10
 * @param adj   邻接矩阵，adj[i][j] == 1 表示节点 i 和 j 之间有边
11
 */
12
void bfs(int n, int start, const vector<vector<int>> &adj) {
13
    vector<bool> visited(n + 1, false);   // 访问标记数组
14
    queue<int> q;                         // BFS 用到的队列
15

16
    visited[start] = true;  // 标记起点已访问
17
    q.push(start);           // 起点入队
18

19
    cout << "BFS 遍历顺序：";
20
    while (!q.empty()) {
21
        int node = q.front();  // 取出队首节点
22
        q.pop();               // 队首出队
23
        cout << node << " ";
24

25
        // 遍历邻接矩阵第 node 行，找出所有邻居
26
        for (int j = 1; j <= n; j++) {
27
            if (adj[node][j] && !visited[j]) {
28
                visited[j] = true;  // 标记为已访问
29
                q.push(j);           // 邻居入队
30
            }
31
        }
32
    }
33
    cout << endl;
34
}
35

36
int main() {
37
    int n = 7;  // 图中节点总数（节点编号 1~7）
38
    // 使用邻接矩阵存储图，adj[i][j] == 1 表示 i 和 j 之间有边
39
    vector<vector<int>> adj(n + 1, vector<int>(n + 1, 0));
40

41
    // 根据示例图片构建无向图（无向图需双向标记）
42
    adj[1][2] = adj[2][1] = 1;
43
    adj[1][3] = adj[3][1] = 1;
44
    adj[1][4] = adj[4][1] = 1;
45
    adj[2][6] = adj[6][2] = 1;
46
    adj[3][7] = adj[7][3] = 1;
47
    adj[5][6] = adj[6][5] = 1;
48
    adj[6][7] = adj[7][6] = 1;
49

50
    bfs(n, 1, adj);  // 从节点 1 开始 BFS
51

52
    return 0;
53
}