首页 > 编程笔记 > C++笔记 阅读：97

图的深度优先搜索和广度优先搜索（C++实现）

图的存储方法主要包括邻接矩阵、邻接表、边集数组、邻接多重表等，遍历图的方法有 2 种，分别是深度优先搜索和广度优先搜索。

深度优先搜索

深度优先搜索（DFS）从图的某个顶点开始，沿着一条路径直到不能继续为止，然后返回并尝试探索其他的路径。直观地感受一下此搜索：我们尽可能深地探索每个可能的路径，直到找到解决方案或确定没有解决方案。

具体步骤如下：
深度优先搜索的特点如下：
深度优先搜索适用于解决一些问题，如寻找路径、检查图的连通性等。

以下代码实现了一个基于邻接表的深度优先搜索算法，用于遍历无向图： 
#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 105;               // 最大顶点数
vector<int> adjList[MAXN];          // 邻接表
bool visited[MAXN];                 // 访问标记
int n, m;                           // n：顶点数，m：边数

void dfs(int u) {
    visited[u] = true;              // 标记顶点 u 为已访问
    cout << u << " ";               // 处理顶点 u
    for (int v : adjList[u]) {      // 遍历邻接顶点
        if (!visited[v]) {
            dfs(v);                 // 递归访问相邻的未被访问的顶点
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adjList[u].push_back(v);    // 对于无向图
        adjList[v].push_back(u);    // 对于无向图
    }
    cout << "DFS遍历结果：";
    dfs(1);                         // 从顶点 1 开始 DFS
    cout << endl;
    return 0;
}
代码说明：

广度优先搜索

广度优先搜索（BFS）从图的某个顶点开始，先访问其所有的邻接顶点，然后逐层访问下去。广度优先搜索就像是一波波水从起始顶点向外扩散，直到把终止顶点找到为止。

具体步骤如下：
广度优先搜索的特点如下：
广度优先搜索适用于解决一些问题，如寻找最短路径、检查图的连通性等。

以下代码实现了一个基于邻接表的广度优先搜索算法，用于遍历无向图： 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 105;               // 最大顶点数
vector<int> adjList[MAXN];          // 邻接表
bool visited[MAXN];                 // 访问标记
int n, m;                           // n：顶点数，m：边数

void bfs(int start) {
    queue<int> q;
    visited[start] = true;          // 标记起点已访问
    q.push(start);                  // 起点入队
    while (!q.empty()) {            // 当队列不为空时循环
        int u = q.front();          // 取出队首顶点
        q.pop();
        cout << u << " ";           // 处理顶点 u
        for (int v : adjList[u]) {  // 遍历邻接顶点
            if (!visited[v]) {      // 若未访问
                visited[v] = true;  // 标记为已访问
                q.push(v);          // 将未被访问的相邻顶点加入队列
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {   // 读入 m 条边
        int u, v;
        cin >> u >> v;
        adjList[u].push_back(v);    // 对于无向图
        adjList[v].push_back(u);    // 对于无向图
    }
    cout << "BFS遍历结果：";
    bfs(1);                         // 从顶点 1 开始 BFS
    cout << endl;
    return 0;
}
首先定义了一个常量 MAXN，表示最大顶点数；然后创建了一个邻接表 adjList 来存储图中的边信息，并定义一个访问标记数组 visited 来记录每个顶点是否被访问过。接着，定义了两个整数变量 n 和 m，分别表示顶点数和边数。

在 bfs() 函数中，使用一个队列 q 来存储待访问的顶点。首先，将起始顶点 start 标记为已访问并将它加入队列。然后进入一个循环，当队列不为空时，取出队首元素 u 并处理（输出）。接着，遍历与 u 相邻的所有顶点 v，如果 v 未被访问过，则将其标记为已访问并加入队列。

总结

如果需要搜索一个具体的路径，DFS 可能是更好的选择。如果需要寻找等权图中的最短路径，BFS 通常更适合。

相关文章