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 <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

// 深度优先搜索函数 (DFS)
// 从当前节点 `node` 开始访问，并递归访问其所有相邻的未访问节点
void DFS(char node, unordered_map<char, vector<char>>& graph, unordered_set<char>& visited) {
    // 标记当前节点为已访问
    visited.insert(node);
    // 输出当前节点（此处可以进行自定义的处理，像打印或其他操作）
    cout << node << " ";  

    // 遍历该节点的所有相邻节点
    for (char neighbor : graph[node]) {
        // 如果相邻节点未访问过，则递归调用 DFS 访问该相邻节点
        if (visited.find(neighbor) == visited.end()) {
            DFS(neighbor, graph, visited);  // 递归调用 DFS
        }
    }
}

// 遍历整个非联通图的DFS
// 对于图中的每一个顶点，如果该顶点未访问过，执行 DFS 来遍历与其相连的部分
void DFSForDisconnectedGraph(unordered_map<char, vector<char>>& graph) {
    // 创建一个集合，用于记录哪些节点已经访问过
    unordered_set<char> visited;
    
    // 遍历图中的所有顶点（unordered_map 的每个键）
    for (auto& pair : graph) {
        char node = pair.first;  // 当前顶点
        // 如果当前顶点未访问过，则从该顶点开始进行 DFS
        if (visited.find(node) == visited.end()) {
            // 从一个新的连通分量的顶点开始新的 DFS
            cout << "Starting new DFS from node: " << node << endl;
            DFS(node, graph, visited);  // 对该连通分量进行DFS遍历
            cout << endl;  // DFS 完成后换行，以区分不同的连通分量
        }
    }
}

int main() {
    // 使用邻接表表示图：unordered_map<char, vector<char>>，表示图中每个顶点及其相邻顶点
    unordered_map<char, vector<char>> graph;
    
    // 定义图的边
    graph['a'] = {'b'};   // 顶点 a 和 b 相连
    graph['b'] = {'a', 'd'};  // 顶点 b 与 a 和 d 相连
    graph['c'] = {'e'};   // 顶点 c 与 e 相连
    graph['d'] = {'b'};   // 顶点 d 与 b 相连
    graph['e'] = {'c'};   // 顶点 e 与 c 相连

    // 调用 DFSForDisconnectedGraph 对非联通图进行遍历
    DFSForDisconnectedGraph(graph);

    return 0;
}

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
#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

// 广度优先搜索函数
void bfs(const unordered_map<char, vector<char>>& graph, char start) {
    // 用于存储待访问节点的队列
    queue<char> q;
    // 用于标记已访问的节点
    unordered_set<char> visited;

    // 将起始节点标记为已访问并加入队列
    visited.insert(start);
    q.push(start);

    // 开始遍历
    while (!q.empty()) {
        // 取出队列中的当前节点
        char node = q.front();
        q.pop();

        // 输出当前节点
        cout << "Visited: " << node << endl;

        // 遍历该节点的所有邻接节点
        for (char neighbor : graph.at(node)) {
            // 如果该邻接节点尚未访问过，加入队列并标记为已访问
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
}

int main() {
    // 图的邻接表表示法
    unordered_map<char, vector<char>> graph = {
        {'a', {'b', 'c'}},
        {'b', {'a', 'd', 'e'}},
        {'c', {'a', 'f'}},
        {'d', {'b'}},
        {'e', {'b', 'f'}},
        {'f', {'c', 'e'}}
    };

    // 从节点 'a' 开始执行 BFS
    bfs(graph, 'a');

    return 0;
}

访问顺序的区别示例

以一个简单的图为例：

1
2
3
4
5
    a
   / \
  b   c
 / \   \
d   e   f
  • DFS 访问顺序（从节点 a 开始）：a, b, d, e, c, f
    • 先从 a 开始，访问 b，然后继续到 d，没有其他未访问的邻接节点后回溯到 b，再访问 e，继续回溯到 a，然后访问 c，最后访问 f。
  • BFS 访问顺序（从节点 a 开始）：a, b, c, d, e, f
    • 先从 a 开始，访问其所有邻接节点 b 和 c，然后继续访问 b 和 c 的所有邻接节点 d, e, f。