图论核心知识点笔记

一、图的存储方式

图的存储核心是记录“顶点”与“边”的关联关系，需根据图的密度（边数/顶点数²）选择合适方式：

1. 邻接矩阵

  • 实现原理：用二维数组 graph[i][j] 表示顶点间关系
    • 无权图：graph[i][j] = 1 表示顶点i与j有边，0 表示无边；
    • 加权图：graph[i][j] = 边的权重（无边时设为无穷大）；
    • 有向图：graph[i][j] 仅表示“i→j”的边，方向不同值独立。
  • 优缺点：
    ✅ 优点：查询两点是否连通、修改边权效率高（O(1)）；
    ❌ 缺点：空间复杂度O(n²)（n为顶点数），稀疏图浪费空间。
  • 适用场景：稠密图（边数接近n²）、需频繁判断两点连通性的场景。

2. 邻接表

  • 实现原理：用“数组+链表/vector”存储，数组下标对应顶点，每个元素存储该顶点的所有邻接顶点（及边权）。
    例：vector<vector<int>> adj(n)，adj[i] 存储顶点i的所有邻接顶点编号。
  • 优缺点：
    ✅ 优点：空间复杂度O(n+m)（m为边数），稀疏图高效；遍历某顶点所有邻接边方便；
    ❌ 缺点：查询两点是否连通需遍历邻接表（O(度)，度为顶点的边数）。
  • 适用场景：稀疏图（边数远小于n²）、需频繁遍历邻接边的场景（如DFS/BFS、最短路径算法）。

二、图的遍历算法

遍历是图论基础操作，核心是“不重复访问顶点”，为后续复杂算法提供支撑：

1. 深度优先搜索（DFS）

  • 核心思想：“不撞南墙不回头”——从起点出发，沿一条路径走到尽头，回溯后探索其他路径。
  • 实现方式：
    • 递归版：利用函数栈回溯，代码简洁；
    • 迭代版：用栈存储待访问顶点，避免递归栈溢出（适用于顶点数多的图）。
  • 关键步骤： 
    1. 标记当前顶点为“已访问”；  
2. 遍历当前顶点的所有邻接顶点，对未访问的顶点递归/迭代调用DFS；  
3. 回溯时继续处理未探索的邻接顶点。
  • 时间复杂度：
    • 顶点的访问 ()：
      • 在 BFS 过程中，每个顶点仅会被放入队列一次，并从队列中弹出一次。
      • 通过“标记已访问”的操作，确保了算法不会陷入死循环或重复处理同一个节点。
    • 边的遍历 ()：
      • 当一个顶点从队列出队时，算法会扫描其所有的邻接边以寻找尚未访问的邻接点。
      • 对于有向图，每条边会被检查 次；对于无向图，每条边会被检查 次（从两个端点各检查一次）。在渐进时间复杂度（Big O）中，这都记为 。
  • 应用场景：判断图中是否存在路径、寻找环、拓扑排序（DFS版）、连通分量计数（无向图）。
  • DFS中边的分类：
    • 树边 (Tree Edge)
      • 定义：在 DFS 过程中，通过搜索发现尚未访问的顶点时所经过的边。
      • 特点：树边构成了深度优先搜索树本身。
      • 判断：如果边 是树边，则 是在搜索 时被发现的。
    • 后向边 (Back Edge)
      • 定义：指向 DFS 树中其祖先节点的边（连接顶点 到其在 DFS 树中的祖先 ）。
      • 特点：后向边预示着图中存在环。在无向图中，后向边通常与树边统称为“回路的一部分”；在有向图中，它是判定有向无环图（DAG）的关键。
      • 自环：自环（指向自身的边）也被视为后向边。
    • 前向边 (Forward Edge)
      • 定义：指向 DFS 树中其后代节点的非树边（连接顶点 到其在 DFS 树中的后代 ）。
      • 判断：边 中， 已经是已访问状态，且在 DFS 树中 是 的后代，但 并不是直接发现 的那条路径。
    • 横向边 (Cross Edge)
      • 定义：连接两个不具有祖先/后代关系的顶点的边。
      • 特点：
        • 它可以连接同一棵 DFS 树中两个互不为祖先的子树节点。
        • 它也可以连接来自不同 DFS 树（森林中）的两个节点。
      • 判断：在有向图中，如果 访问 时， 已经处理完毕（已回溯），且 不是 的后代，则该边为横向边。
/**
 * @brief 使用栈实现的深度优先搜索 (DFS) 迭代版
 * @param adj 图的邻接表
 * @param start_node 起始顶点编号
 */
void DFS_iterative(const AdjacencyList& adj, int start_node) {
    int N = adj.size();
    if (N == 0) return;

    std::vector<bool> visited(N, false);
    std::stack<int> s; // 核心：使用栈存储待访问顶点

    std::cout << "DFS 访问顺序 (迭代版从 " << start_node << "): ";

    // 1. 起点入栈
    s.push(start_node);
    
    // 注意：我们只在顶点出栈时进行访问操作，确保每个顶点只访问一次。
    // 或者，在入栈时标记并访问，但这样可能会改变传统 DFS 的访问顺序。
    // 这里采用更标准的方式：入栈时不访问，出栈（或第一次遇到）时访问。

    while (!s.empty()) {
        int u = s.top();
        s.pop();

        // 避免重复访问（即使在入栈时没有访问，出栈时也要检查）
        if (visited[u]) {
            continue;
        }

        // 2. 标记当前顶点并访问
        visited[u] = true;
        print_visit(u); 

        // 3. 遍历当前顶点的所有邻接顶点
        // 注意：栈是 LIFO（后进先出），为了保持与递归版（通常优先访问编号较小的邻接点）
        // 相似的顺序，我们通常需要逆序遍历邻接表，
        // 这样编号较小的邻接点会最后入栈，从而最先出栈。
        // （如果不需要严格匹配顺序，正序遍历也可。）
        
        // 此处采用正序遍历，如果邻接表是 {1, 2}，则先入栈 2，再入栈 1，导致先访问 1。
        // 这样可以模拟递归 DFS 的行为。
        for (int i = adj[u].size() - 1; i >= 0; --i) {
            int v = adj[u][i];
            if (!visited[v]) {
                s.push(v);
            }
        }
    }
    std::cout << std::endl;
}

/**
 * @brief 递归实现的深度优先搜索 (DFS)
 * @param adj 图的邻接表
 * @param u 当前访问的顶点编号
 * @param visited 顶点的访问状态标记
 */
void DFS_recursive(const AdjacencyList& adj, int u, std::vector<bool>& visited) {
    
    // 1. 标记当前顶点并访问
    visited[u] = true;
    print_visit(u); 

    // 2. 遍历当前顶点的所有邻接顶点
    for (int v : adj[u]) {
        // 对未访问的邻接顶点递归调用 DFS
        if (!visited[v]) {
            DFS_recursive(adj, v, visited);
        }
    }
    // 3. (隐含的回溯：函数返回时，自动回溯到上一个顶点)
}

// DFS 入口函数
void DFS_Traversal(const AdjacencyList& adj, int start_node) {
    int N = adj.size();
    if (N == 0) return;
    
    std::vector<bool> visited(N, false);
    
    std::cout << "DFS 访问顺序 (从 " << start_node << "): ";
    DFS_recursive(adj, start_node, visited);
    std::cout << std::endl;
    
    // 如果是处理连通分量，还需要检查是否有未访问的顶点，并从它们开始新的 DFS
}

// DFS 入口函数
void DFS_Traversal(const AdjacencyList& adj, int start_node) {
    int N = adj.size();
    if (N == 0) return;
    
    std::vector<bool> visited(N, false);
    
    // 递归版调用
    std::cout << "DFS 访问顺序 (递归版从 " << start_node << "): ";
    DFS_recursive(adj, start_node, visited);
    std::cout << std::endl;
    
    // 迭代版调用
    DFS_iterative(adj, start_node);

    // 如果是处理连通分量，还需要检查是否有未访问的顶点，并从它们开始新的 DFS
}

2. 广度优先搜索（BFS）

  • 核心思想：“逐层扩散”——从起点出发，先访问起点的所有邻接顶点（第一层），再访问邻接顶点的邻接顶点（第二层），依次类推。
  • 实现方式：用队列（先进先出）存储待访问顶点，保证层次遍历顺序。
  • 关键步骤： 
    1. 起点入队，标记为“已访问”；  
2. 队列非空时，出队队首顶点，遍历其所有邻接顶点；  
3. 未访问的邻接顶点标记后入队，重复步骤2。
  • 时间复杂度：
    • 顶点的访问 ()：
      • 在 BFS 过程中，每个顶点仅会被放入队列一次，并从队列中弹出一次。
      • 通过“标记已访问”的操作，确保了算法不会陷入死循环或重复处理同一个节点。
    • 边的遍历 ()：
      • 当一个顶点从队列出队时，算法会扫描其所有的邻接边以寻找尚未访问的邻接点。
      • 对于有向图，每条边会被检查 次；对于无向图，每条边会被检查 次（从两个端点各检查一次）。在渐进时间复杂度（Big O）中，这都记为 。
  • 对于没有权重的图，BFS存储的就是最短路径。
  • 应用场景：无权图的最短路径、层次遍历、连通分量计数（无向图）、拓扑排序（BFS版）。
/**
 * @brief 使用队列实现的广度优先搜索 (BFS)
 * @param adj 图的邻接表
 * @param start_node 起始顶点编号
 */
void BFS_Traversal(const AdjacencyList& adj, int start_node) {
    int N = adj.size();
    if (N == 0) return;

    std::vector<bool> visited(N, false);
    std::queue<int> q; // 核心：使用队列存储待访问顶点

    std::cout << "BFS 访问顺序 (从 " << start_node << "): ";

    // 1. 起点入队，标记为已访问
    q.push(start_node);
    visited[start_node] = true;

    // 2. 队列非空时循环
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        print_visit(u); // 访问出队的顶点

        // 遍历 u 的所有邻接顶点
        for (int v : adj[u]) {
            // 3. 未访问的邻接顶点标记后入队
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    std::cout << std::endl;
}

三、图的核心应用算法

1. 最小生成树（MST）

  • 生成树：所以顶点均连在一起，但不存在回路的图
  • 问题定义：针对“无向加权连通图”，找到一棵包含所有顶点、边权和最小的生成树（无环，边数=n-1）。
  • 核心目标：连接所有顶点，总权值最小，无环。

（1）Prim算法

  • 核心思想：“加点法”——从任意起点出发，每次选择“连接当前生成树与非树顶点”的最小权边，将该非树顶点加入生成树，重复至所有顶点加入。
  • 实现要点：
    • 用数组 dist[] 记录每个非树顶点到生成树的最小距离；
    • 每次选 dist[] 中最小的顶点加入树，更新其他顶点的 dist[]。
  • 时间复杂度：O(m log n)（堆优化版）。
  • 适用场景：稠密图（顶点少、边多），堆优化后也适用于稀疏图。

（2）Kruskal算法

  • 核心思想：“加边法”——按边权从小到大排序，依次选边，若边的两个顶点不在同一连通分量（用并查集判断），则加入生成树，重复至生成树有n-1条边。
  • 实现要点：
    • 依赖并查集（DSU）判断环（路径压缩+按秩合并优化）；
    • 边排序是核心步骤（时间复杂度O(m log m)）。
  • 时间复杂度：O(m log m)（主要开销在边排序）。
  • 适用场景：稀疏图（边少，排序开销小）。

2. 最短路径

（1）Dijkstra算法

  • 问题场景：单源最短路径（从一个起点到所有其他顶点）、边权非负。
  • 核心思想：
    • ==若顶点 U 是当前「未确定最短路径」的顶点中，距离起点 S 最近的那个，那么 S→U 的最短路径已经确定（后续不会再找到更短的路径）==。
    • 确定最短路径顶点 → 用该顶点更新邻接顶点的距离 → 重复直到所有顶点都确定
  • 实现要点：
    • 关键数组：dist []（距离记录数组）
      • 作用：存储「起点 S 到每个顶点的当前最短距离」。
      • 当我们确定顶点 U 的最短路径后，遍历 U 的所有邻接顶点 V。如果 dist[U] + 边权(U→V) < dist[V]，说明找到了一条从 S→U→V 的更短路径，就把 dist[V] 更新为这个更小的值（这个过程叫「松弛操作」）。
  • 优先队列（小根堆）：高效找 “最近未确定顶点”
    • 作用：存储「未确定最短路径的顶点 + 其当前距离起点的距离」，核心是 O (log n) 时间内快速取出当前距离最小的顶点。
  • 辅助数组：visited []（可选，标记已确定顶点）
    • 当从堆中取出顶点 U 时，先检查 visited[U]。如果是 true，说明已经处理过更优路径，直接跳过；如果是 false，则处理 U 的邻接顶点，处理完后设 visited[U] = true。
  • 时间复杂度：O(m log n)（堆优化版）。
  • 注意事项：不能处理负权边（贪心策略会失效）。
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

const int INF = INT_MAX;

// 边的结构体：to是目标顶点，weight是边权
struct Edge {
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w) {}
};

// Dijkstra算法实现
// graph: 邻接表表示的图
// start: 起点
// n: 顶点总数
vector<int> dijkstra(const vector<vector<Edge>>& graph, int start, int n) {
    // 1. 初始化距离数组，所有距离设为无穷大
    vector<int> dist(n, INF);
    // 起点到自身的距离为0
    dist[start] = 0;

    // 2. 优先队列（小根堆），存储 (当前距离, 顶点)
    // 优先队列会根据当前距离从小到大排序
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    // 3. 标记已确定最短路径的顶点
    vector<bool> visited(n, false);

    while (!pq.empty()) {
        // 4. 取出当前距离最小的顶点
        int current_dist = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        // 如果该顶点已处理过，直接跳过
        if (visited[u]) continue;

        // 标记该顶点为已处理
        visited[u] = true;

        // 5. 遍历该顶点的所有邻接边，进行松弛操作
        for (const Edge& edge : graph[u]) {
            int v = edge.to;
            int weight = edge.weight;

            // 如果找到更短的路径
            if (dist[u] != INF && dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                // 将更新后的距离和顶点加入优先队列
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}

int main() {
    // 示例图
    // 顶点编号：0, 1, 2, 3
    // 边：
    // 0->1 (weight=4)
    // 0->2 (weight=1)
    // 2->1 (weight=2)
    // 1->3 (weight=1)
    // 2->3 (weight=5)
    int n = 4;
    vector<vector<Edge>> graph(n);
    graph[0].emplace_back(1, 4);
    graph[0].emplace_back(2, 1);
    graph[2].emplace_back(1, 2);
    graph[1].emplace_back(3, 1);
    graph[2].emplace_back(3, 5);

    int start = 0;
    vector<int> shortest_distances = dijkstra(graph, start, n);

    cout << "从起点 " << start << " 到各顶点的最短距离：" << endl;
    for (int i = 0; i < n; ++i) {
        if (shortest_distances[i] == INF) {
            cout << "到顶点 " << i << "：不可达" << endl;
        } else {
            cout << "到顶点 " << i << "：" << shortest_distances[i] << endl;
        }
    }

    return 0;
}

（2）Bellman-Ford算法

  • 问题场景：单源最短路径、允许负权边、检测负权环。
  • 核心思想：
    • 松弛操作：对于边 u→v（边权为 w），如果当前起点到 u 的距离 dist[u] 加上边权 w，比起点到 v 的当前距离 dist[v] 更小，就更新 dist[v] = dist[u] + w。
    • 为什么要迭代 n-1 次：
      • 最短路径不会包含环（如果包含正权环，去掉环路径更短；如果包含负权环，就没有最短路径），因此最短路径是「无环路径」，最多经过所有顶点一次，即 n-1 条边。
      • 第 n-1 次迭代：能找到所有 “从起点出发，经过最多 n-1 条边” 的最短路径（即所有可能的最短路径）。
  • 时间复杂度：。
  • 适用场景：需处理负权边或检测负权环的场景（如“判断图中是否存在总权为负的环”）。
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

const int INF = INT_MAX;

// 边的结构体：from是起点，to是终点，weight是边权
struct Edge {
    int from;
    int to;
    int weight;
    Edge(int f, int t, int w) : from(f), to(t), weight(w) {}
};

// Bellman-Ford算法实现
// edges: 所有边的列表
// start: 起点
// n: 顶点总数
// has_negative_cycle: 用于返回是否存在负权环
vector<int> bellman_ford(const vector<Edge>& edges, int start, int n, bool& has_negative_cycle) {
    // 1. 初始化距离数组
    vector<int> dist(n, INF);
    dist[start] = 0;

    // 2. 进行 n-1 次松弛操作
    for (int i = 0; i < n - 1; ++i) {
        bool updated = false; // 标记本次迭代是否有更新
        for (const Edge& edge : edges) {
            int u = edge.from;
            int v = edge.to;
            int weight = edge.weight;

            // 如果u可达，且通过u到v的路径更短
            if (dist[u] != INF && dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                updated = true;
            }
        }
        // 如果本次迭代没有任何更新，说明所有最短路径都已找到，可以提前退出
        if (!updated) break;
    }

    // 3. 检测是否存在负权环
    has_negative_cycle = false;
    for (const Edge& edge : edges) {
        int u = edge.from;
        int v = edge.to;
        int weight = edge.weight;

        // 如果在 n-1 次迭代后仍然可以松弛，说明存在负权环
        if (dist[u] != INF && dist[v] > dist[u] + weight) {
            has_negative_cycle = true;
            break;
        }
    }

    return dist;
}

int main() {
    // 示例图（包含负权边）
    // 顶点编号：0, 1, 2, 3
    int n = 4;
    vector<Edge> edges;
    edges.emplace_back(0, 1, 4);
    edges.emplace_back(0, 2, 1);
    edges.emplace_back(2, 1, 2);
    edges.emplace_back(1, 3, 1);
    edges.emplace_back(2, 3, -5); // 负权边

    int start = 0;
    bool has_negative_cycle;

    vector<int> shortest_distances = bellman_ford(edges, start, n, has_negative_cycle);

    if (has_negative_cycle) {
        cout << "图中存在负权环，无法计算最短路径！" << endl;
    } else {
        cout << "从起点 " << start << " 到各顶点的最短距离：" << endl;
        for (int i = 0; i < n; ++i) {
            if (shortest_distances[i] == INF) {
                cout << "到顶点 " << i << "：不可达" << endl;
            } else {
                cout << "到顶点 " << i << "：" << shortest_distances[i] << endl;
            }
        }
    }

    cout << "\n--- 测试存在负权环的图 ---" << endl;
    // 示例图（包含负权环）
    // 顶点编号：0, 1, 2
    int n2 = 3;
    vector<Edge> edges2;
    edges2.emplace_back(0, 1, 1);
    edges2.emplace_back(1, 2, -2);
    edges2.emplace_back(2, 1, -1); // 1->2->1 形成负权环

    vector<int> shortest_distances2 = bellman_ford(edges2, 0, n2, has_negative_cycle);

    if (has_negative_cycle) {
        cout << "图中存在负权环，无法计算最短路径！" << endl;
    } else {
        // ... 输出逻辑 ...
    }

    return 0;
}

（3）Floyd-Warshall算法

  • 问题场景：多源最短路径（所有顶点间的最短路径）、允许负权边（无负权环）。
  • 核心思想：动态规划——dp[i][j] 表示顶点i到j的最短路径，通过中间顶点k更新：dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])。
  • 实现要点：
    • 用二维数组 dp 存储最短路径矩阵，初始化为邻接矩阵；
    • 三层循环：枚举中间顶点k→枚举起点i→枚举终点j。
  • 时间复杂度：O(n³)。
  • 适用场景：顶点数少（n≤100）的多源路径问题（代码简洁，无需复杂数据结构）。
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

const int INF = INT_MAX;

// Floyd-Warshall算法实现
// graph: 邻接矩阵表示的图
// n: 顶点总数
vector<vector<int>> floyd_warshall(vector<vector<int>> graph, int n) {
    // dp[i][j] 表示从顶点i到顶点j的最短距离
    vector<vector<int>> dp(n, vector<int>(n));

    // 1. 初始化dp矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            dp[i][j] = graph[i][j];
        }
    }

    // 2. 核心三层循环：枚举中间顶点k，起点i，终点j
    for (int k = 0; k < n; ++k) { // k是中间顶点
        for (int i = 0; i < n; ++i) { // i是起点
            for (int j = 0; j < n; ++j) { // j是终点
                // 如果i到k可达，且k到j可达，并且i->k->j的路径比i->j的路径更短
                if (dp[i][k] != INF && dp[k][j] != INF && dp[i][j] > dp[i][k] + dp[k][j]) {
                    dp[i][j] = dp[i][k] + dp[k][j];
                }
            }
        }
    }

    return dp;
}

int main() {
    // 示例图的邻接矩阵
    // 顶点编号：0, 1, 2, 3
    // 0表示自身，INF表示不可达
    int n = 4;
    vector<vector<int>> graph = {
        {0, 4, 1, INF},
        {INF, 0, INF, 1},
        {INF, 2, 0, 5},
        {INF, INF, INF, 0}
    };

    vector<vector<int>> shortest_paths = floyd_warshall(graph, n);

    cout << "所有顶点间的最短路径矩阵：" << endl;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (shortest_paths[i][j] == INF) {
                cout << "INF\t";
            } else {
                cout << shortest_paths[i][j] << "\t";
            }
        }
        cout << endl;
    }

    return 0;
}

3. 拓扑排序

  • 问题场景：有向无环图（DAG），输出一个“所有边的起点在终点之前”的顶点序列（若有环则无法拓扑排序）。
  • 核心目标：验证图是否为 DAG，或生成符合依赖关系的线性序列。
  • 时间复杂度：，其中 是顶点数， 是边数。每个顶点入队/递归一次，每条边被扫描一次。
  • 实现方式：
    （1）BFS 版（Kahn 算法/入度表法）：
      1.统计所有顶点的入度，入度为 0 的顶点入队；
  2.出队顶点并加入结果序列，遍历其所有出边，对应邻接顶点的入度减 1；
  3.若邻接顶点入度变为 0 则入队，重复至队空；
  4.若最终输出顶点数 $\neq$ 总顶点数，说明图中存在环。
    （2）DFS 版（回溯记录法）：
      1.使用状态数组标记顶点（未访问、访问中、已完成）；
  2.对每个未访问顶点进行 DFS：若遇到“访问中”的节点，说明存在**后向边**（有环）；
  3.在顶点遍历结束（即将回溯）时，将其压入结果栈或列表；
  4.最终将结果列表**逆序**输出，即为拓扑序列。
  • 应用场景：任务调度（如先修课规划）、编译依赖分析、项目进度管理。
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>

using namespace std;

/**
 * 1. 拓扑排序 BFS 版（Kahn 算法 / 入度表法）
 * 时间复杂度: O(V + E)
 */
vector<int> topologicalSortBFS(const vector<vector<int>>& graph, int n) {
    vector<int> inDegree(n, 0);
    vector<int> topoOrder;

    // 统计入度
    for (int u = 0; u < n; ++u) {
        for (int v : graph[u]) inDegree[v]++;
    }

    queue<int> q;
    for (int i = 0; i < n; ++i) {
        if (inDegree[i] == 0) q.push(i);
    }

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

        for (int v : graph[u]) {
            if (--inDegree[v] == 0) q.push(v);
        }
    }

    if (topoOrder.size() != n) return {}; // 发现环
    return topoOrder;
}

/**
 * 2. 拓扑排序 DFS 版
 * 时间复杂度: O(V + E)
 */
bool dfs(int u, const vector<vector<int>>& graph, vector<int>& state, vector<int>& result) {
    state[u] = 1; // 标记为：正在访问（灰色）
    
    for (int v : graph[u]) {
        if (state[v] == 1) return false; // 发现后向边，说明有环
        if (state[v] == 0) {
            if (!dfs(v, graph, state, result)) return false;
        }
    }
    
    state[u] = 2; // 标记为：已完成访问（黑色）
    result.push_back(u); // 回溯前加入结果
    return true;
}

vector<int> topologicalSortDFS(const vector<vector<int>>& graph, int n) {
    vector<int> state(n, 0); // 0:未访问, 1:访问中, 2:已完成
    vector<int> result;

    for (int i = 0; i < n; ++i) {
        if (state[i] == 0) {
            if (!dfs(i, graph, state, result)) return {}; // 存在环
        }
    }

    reverse(result.begin(), result.end()); // 逆序得到拓扑序列
    return result;
}

// --- 测试代码 ---
void printOrder(const string& method, const vector<int>& order) {
    if (order.empty()) {
        cout << method << ": 图中存在环，无法进行拓扑排序！" << endl;
    } else {
        cout << method << " 序列：";
        for (int u : order) cout << u << " ";
        cout << endl;
    }
}

int main() {
    int n = 5;
    vector<vector<int>> graph(n);
    graph[0] = {1, 2};
    graph[1] = {3};
    graph[2] = {3};
    graph[3] = {4};

    cout << "--- DAG 测试 ---" << endl;
    printOrder("BFS", topologicalSortBFS(graph, n));
    printOrder("DFS", topologicalSortDFS(graph, n));

    cout << "\n--- 有环图测试 ---" << endl;
    int n2 = 3;
    vector<vector<int>> graph2(n2);
    graph2[0] = {1}; graph2[1] = {2}; graph2[2] = {0};
    
    printOrder("BFS", topologicalSortBFS(graph2, n2));
    printOrder("DFS", topologicalSortDFS(graph2, n2));

    return 0;
}

4.连通分量

（1）连通分量的定义

对于无向图而言，连通分量是图的一个极大连通子图。

  • 连通性：在该子图中，任意两个顶点之间都存在路径相连。
  • 极大性：如果再加入原图中的任何其他顶点，该子图将不再连通。

（2）求连通分量的两种主要算法

求连通分量的本质是遍历图。通过从每一个未访问的顶点出发进行一次完整的搜索，每次搜索所覆盖的所有节点就属于同一个连通分量。
(1) 深度优先搜索 (DFS) 法

  • 逻辑：
    1. 遍历图中的所有顶点。
    2. 如果当前顶点未被访问，则以该点为起点启动一次 DFS。
    3. DFS 递归过程中访问到的所有顶点都被标记为属于同一个连通分量。
    4. 重复上述过程，直到所有顶点都被访问。

  • 优点：代码实现简单（递归），适合统计连通分量数量及记录成员。

    (2) 广度优先搜索 (BFS) 法

  • 逻辑：
    1. 遍历图中的所有顶点。
    2. 如果当前顶点未被访问，则将其入队并启动一次 BFS。
    3. 利用队列逐层扩散，所有出队并标记过的顶点属于同一个连通分量。
    4. 重复直到所有点处理完毕。
  • 优点：迭代实现，在处理超大规模图时不会有递归栈溢出的风险。

两种方法的时间复杂度：

  • 邻接表：**
  • 邻接矩阵：