c++图论(三)之图的遍历

在 C++ 中实现图的遍历主要有两种经典算法：深度优先搜索（DFS） 和 广度优先搜索（BFS）。以下是两种遍历方法的实现原理、代码示例及对比分析：

一、深度优先搜索（DFS）

核心思想

• 递归或栈实现：从起点出发，尽可能深入访问未探索的邻接顶点，回溯后继续搜索。
• 应用场景：路径查找、连通性检测、拓扑排序、回溯问题等。

C++ 实现（邻接表存储，递归与非递归版本）

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// 邻接表表示的图（无权图）
vector<vector<int>> adjList;

// 递归版 DFS
void dfsRecursive(int u, vector<bool>& visited) {
    visited[u] = true;
    cout << u << " ";  // 访问顶点
    for (int v : adjList[u]) {
        if (!visited[v]) {
            dfsRecursive(v, visited);
        }
    }
}

// 非递归版 DFS（栈实现）
void dfsIterative(int start) {
    vector<bool> visited(adjList.size(), false);
    stack<int> s;
    s.push(start);
    visited[start] = true;

    while (!s.empty()) {
        int u = s.top();
        s.pop();
        cout << u << " ";  // 访问顶点

        // 逆序入栈以保证顺序与递归一致
        for (auto it = adjList[u].rbegin(); it != adjList[u].rend(); ++it) {
            int v = *it;
            if (!visited[v]) {
                visited[v] = true;
                s.push(v);
            }
        }
    }
}

int main() {
    // 示例图的邻接表（5 个顶点）
    adjList = {
        {1, 4},    // 顶点 0 的邻居
        {0, 2, 3}, // 顶点 1 的邻居
        {1, 3},    // 顶点 2 的邻居
        {1, 2},    // 顶点 3 的邻居
        {0}        // 顶点 4 的邻居
    };

    vector<bool> visited(adjList.size(), false);
    cout << "递归 DFS: ";
    dfsRecursive(0, visited);  // 输出: 0 1 2 3 4

    cout << "\n非递归 DFS: ";
    dfsIterative(0);           // 输出: 0 4 1 3 2
    return 0;
}

二、广度优先搜索（BFS）

核心思想

• 队列实现：从起点出发，逐层访问所有邻接顶点。
• 应用场景：最短路径（无权图）、社交网络层级分析、连通性检测等。

C++ 实现（邻接表存储）

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 邻接表表示的图（无权图）
vector<vector<int>> adjList;

void bfs(int start) {
    vector<bool> visited(adjList.size(), false);
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";  // 访问顶点

        for (int v : adjList[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

int main() {
    // 示例图的邻接表（同 DFS 示例）
    adjList = {
        {1, 4},    // 顶点 0 的邻居
        {0, 2, 3}, // 顶点 1 的邻居
        {1, 3},    // 顶点 2 的邻居
        {1, 2},    // 顶点 3 的邻居
        {0}        // 顶点 4 的邻居
    };

    cout << "BFS: ";
    bfs(0);  // 输出: 0 1 4 2 3
    return 0;
}

三、DFS 与 BFS 的对比

四、遍历算法的扩展应用

1. 连通分量检测（DFS/BFS）

int countConnectedComponents() {
    int count = 0;
    vector<bool> visited(adjList.size(), false);
    for (int u = 0; u < adjList.size(); ++u) {
        if (!visited[u]) {
            dfsRecursive(u, visited);  // 或调用 BFS
            count++;
        }
    }
    return count;
}

2. 路径记录（BFS 最短路径）

vector<int> shortestPathBFS(int start, int end) {
    vector<bool> visited(adjList.size(), false);
    vector<int> parent(adjList.size(), -1);
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (u == end) break;
        for (int v : adjList[u]) {
            if (!visited[v]) {
                visited[v] = true;
                parent[v] = u;
                q.push(v);
            }
        }
    }

    // 回溯路径
    vector<int> path;
    for (int at = end; at != -1; at = parent[at]) {
        path.push_back(at);
    }
    reverse(path.begin(), path.end());
    return path;  // 若路径为空或起点未访问，则不可达
}

五、总结

• DFS 适合深入探索路径或解决回溯问题，递归实现简洁但可能栈溢出，非递归实现更可控。
• BFS 适合逐层扩散和最短路径问题，队列实现保证了层级顺序。
• 实际应用：根据问题需求选择遍历方式，结合 邻接表 或 邻接矩阵 优化性能。

等等！！如果上面的代码看不懂，就看看下面的模版

DFS：

vector<int> adj[101];
bool visited[101];
void dfs(int u) {
  if (visited[u]) {
    return;
  }
  visited[u] = true;
  // 这里处理 node u
  
  for (auto v: adj[u]) {
    dfs(v);
  }
}

BFS：

queue<int> q;
bool visited[N];
int distance[N];
// 从节点 x 开始搜索
visited[x] = true, distance[x] = 0;
q.push(x);

while (!q.empty()) {
  int u = q.front(); q.pop();

  // 处理节点 u
  for (auto v : adj[u]) {
    // 处理 u 的所有相邻节点
    if (visited[v]) continue;

    visited[v] = true, distance[v] = distance[u]+1;
    q.push(v);
  }
}

明白没？如果还没明白就去请教AI吧