20260228 145107 Cpp 入门第二十一课

第二十一章：图论基础——探索网络的世界 ¶

你好！欢迎来到第二十一章！你有没有坐过地铁？地铁线路图上有许多站点（顶点），站点之间有轨道连接（边），这就构成了一个图。图论就是研究这种由点和线组成的结构的数学分支，它在计算机科学中有着广泛的应用——从社交网络、导航系统到互联网路由。这一章我们就来学习图的基本概念和常用算法！

21.1 图的概念 ¶

21.1.1 什么是图？¶

图由顶点（Vertex）和边（Edge）组成。顶点可以理解为一个个“点”，边是连接两个顶点的“线”。比如：

地铁站是顶点，轨道是边。
微信好友：每个人是顶点，好友关系是边。
城市之间的公路：城市是顶点，公路是边。

21.1.2 图的分类 ¶

无向图：边没有方向，就像双行道。比如好友关系，A认识B，B也认识A。
有向图：边有方向，就像单行道。比如微博关注，A关注B，但B不一定关注A。
带权图：边上有数值，称为权值，表示距离、时间、花费等。比如城市之间的公路长度。

21.1.3 基本术语 ¶

度：与一个顶点相连的边的数量。有向图中还分为入度（指向该顶点的边数）和出度（从该顶点出发的边数）。
路径：从一个顶点到另一个顶点经过的顶点序列。
连通图：任意两个顶点之间都有路径相连。
树：一种特殊的图，没有环，且连通。

21.2 图的存储 ¶

在程序中，我们需要告诉计算机图的结构。常用的存储方式有两种：邻接矩阵和邻接表。

21.2.1 邻接矩阵 ¶

用二维数组 g[i][j] 表示顶点 i 和 j 之间的关系。对于无向图，g[i][j] = 1 表示有边，0 表示无边；对于带权图，g[i][j] 可以存储权值，无边时用无穷大（如 1e9）表示。

优点：简单直观，查找任意两点是否有边很快（O(1)）。
缺点：当顶点很多但边很少时，浪费空间（需要 n² 的空间）。

// 无向图，顶点数 n
int g[100][100] = {0};
// 添加一条边 u - v
g[u][v] = 1;
g[v][u] = 1;

21.2.2 邻接表 ¶

对于每个顶点，用一个列表（如 vector）存储它所有的邻居。这样只存存在的边，节省空间。

优点：节省空间，遍历某个顶点的所有邻居很方便。
缺点：判断两点是否有边需要遍历列表，不如矩阵快。

#include <vector>
using namespace std;

vector<int> adj[100];  // 邻接表，adj[u] 存储 u 的所有邻居
// 添加一条无向边
adj[u].push_back(v);
adj[v].push_back(u);

对于带权图，可以存一个结构体或 pair：

struct Edge {
    int to, weight;
};
vector<Edge> adj[100];
adj[u].push_back({v, w});
adj[v].push_back({u, w});

21.3 图的遍历 ¶

和树一样，图也需要遍历才能访问所有顶点。常用的两种遍历是 DFS 和 BFS。

21.3.1 深度优先搜索（DFS）遍历图 ¶

从一个顶点出发，沿着一条路走到底，然后回溯。需要标记已访问的顶点，避免重复访问。

代码实现（邻接表）：

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

vector<int> adj[100];
bool visited[100];

void dfs(int u) {
    visited[u] = true;
    cout << u << " ";  // 访问顶点
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

int main() {
    int n, m; // n顶点数，m边数
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    // 假设从顶点0开始遍历
    dfs(0);
    return 0;
}

21.3.2 广度优先搜索（BFS）遍历图 ¶

一层一层向外扩展，用队列实现。可以求无权图的最短路径（从起点到每个顶点的最少边数）。

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

vector<int> adj[100];
bool visited[100];
int dist[100];  // 记录到起点的距离

void bfs(int start) {
    queue<int> q;
    visited[start] = true;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

21.4 最短路径问题 ¶

在带权图中，我们经常要问：从顶点 A 到顶点 B 的最短路径是哪条？总权值最小是多少？经典的算法有 Dijkstra（单源，边权非负）和 Floyd（多源）。

21.4.1 Dijkstra 算法 ¶

思想：维护一个距离数组，不断从未确定的顶点中选出当前距离最小的顶点，用它去更新邻居的距离。就像我们不断向外扩散，每次找到最近的点。

适用条件：边权非负。

代码实现（邻接表 + 优先队列优化）：

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

struct Edge {
    int to, weight;
};
vector<Edge> adj[100];
int dist[100];
bool visited[100];

void dijkstra(int start, int n) {
    for (int i = 0; i < n; i++) dist[i] = INT_MAX;
    dist[start] = 0;
    // 优先队列：pair<距离, 顶点>，按距离从小到大
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (Edge e : adj[u]) {
            int v = e.to;
            int w = e.weight;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

解释：优先队列每次取出当前距离最小的顶点，用它更新邻居。因为距离小的点一旦确定就不会再变小（边权非负），所以可以标记已访问。

21.4.2 Floyd-Warshall 算法 ¶

求所有点对之间的最短路径。用三重循环，动态规划思想：允许经过中间节点 k 来更新 i 到 j 的距离。

代码实现：

int g[100][100]; // 邻接矩阵，初始为 INF，对角线为0
int n;

void floyd() {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][k] < INF && g[k][j] < INF)
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
}

21.5 最小生成树 ¶

一个连通的无向图，如果它是一棵树（没有环）且包含所有顶点，就叫生成树。权值之和最小的生成树叫最小生成树。常用于铺设管道、网络布线等。

21.5.1 Prim 算法 ¶

从一个顶点开始，每次选择一条连接已选集合和未选集合的最小权边，将新顶点加入集合。

代码实现（邻接矩阵）：

const int INF = 1e9;
int g[100][100];
int n;

int prim() {
    int dist[100];   // 记录未选顶点到已选集合的最小距离
    bool vis[100] = {false};
    for (int i = 0; i < n; i++) dist[i] = INF;
    dist[0] = 0;
    int total = 0;
    for (int i = 0; i < n; i++) {
        // 选出未选顶点中距离最小的
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!vis[j] && (u == -1 || dist[j] < dist[u]))
                u = j;
        }
        vis[u] = true;
        total += dist[u];
        // 更新邻居的距离
        for (int v = 0; v < n; v++) {
            if (!vis[v] && g[u][v] < dist[v])
                dist[v] = g[u][v];
        }
    }
    return total;
}

21.5.2 Kruskal 算法 ¶

将所有边按权值从小到大排序，然后依次尝试加入，如果加入后不形成环就保留（用并查集判断是否连通）。

代码实现（需要并查集）：

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};
Edge edges[10000];
int parent[100];

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x != y) parent[x] = y;
}

int kruskal(int n, int m) {
    sort(edges, edges + m);
    for (int i = 0; i < n; i++) parent[i] = i;
    int total = 0, cnt = 0;
    for (int i = 0; i < m; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        if (find(u) != find(v)) {
            unite(u, v);
            total += w;
            cnt++;
            if (cnt == n-1) break;
        }
    }
    return total;
}

21.6 编程实例讲解 ¶

实例1：判断图是否连通 ¶

用 DFS 或 BFS 遍历整个图，如果 visited 数组全为 true 则连通。

bool isConnected(int n) {
    dfs(0);
    for (int i = 0; i < n; i++)
        if (!visited[i]) return false;
    return true;
}

实例2：查找图中的环（无向图）¶

用 DFS 时，如果遇到一个已经访问过的邻居且不是父节点，就说明有环。

bool hasCycle(int u, int parent) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            if (hasCycle(v, u)) return true;
        } else if (v != parent) {
            return true; // 遇到非父节点的已访问节点，有环
        }
    }
    return false;
}

实例3：最短路径示例 ¶

输入一个城市交通图（顶点数 n，边数 m），求从城市 0 到城市 n-1 的最短路径长度。

// 直接用 Dijkstra
dijkstra(0, n);
cout << dist[n-1] << endl;

21.7 阶段性编程练习 ¶

练习1：用邻接矩阵和邻接表两种方式存储下面的图，并编写代码遍历所有顶点（DFS和BFS）。
0--1--2 | | 3--4
练习2：实现一个函数，判断有向图中是否存在从 u 到 v 的路径。
练习3：用 Dijkstra 求下面带权图从顶点0到其他顶点的最短距离。
0--(2)--1 | | (4) (1) | | 3--(3)--2
练习4：用 Prim 或 Kruskal 求下面图的最小生成树权值。
0--(1)--1--(2)--2 | | | (3) (4) (5) | | | 3--(2)--4--(1)--5
练习5：实现一个程序，读入一个无向图，输出每个顶点的度。