首页 > 编程笔记 > C++笔记 阅读:1

图的深度优先搜索和广度优先搜索(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 通常更适合。

相关文章