CC++ & Algorithm

图的定义与相关概念

困难3
语言版本：C++
概述：用朋友关系和城市道路的比喻，解释图由顶点和边组成，以及有向图、无向图、权重的意思。

图的定义与相关概念

你有没有玩过“找朋友”的游戏？每个小朋友是一个点，两个人手拉手就形成一条线——这就是图最朴素的模型。在计算机里，图由两部分组成：顶点（Vertex）和边（Edge）。顶点可以看作地图上的城市，边就是连接城市的道路。

如果道路是双向的（A城到B城可以走，B城到A城也可以走），这样的边叫无向边，整个图叫无向图，就像朋友之间互相认识。如果道路是单向的（比如只能从A到B），就叫有向边，图叫有向图，好比单行车道。如果每条道路有长度，就叫做权重，就像高速公路的里程。

举个例子：三个小朋友小明、小红、小刚。小明和小红是朋友，小红和小刚也是朋友，但小明和小刚不是朋友。用无向图表示：顶点有3个，边有2条。如果用C++描述，可以用一个结构体或简单的数组来记录。

#include <iostream>
using namespace std;

int main() {
    // 假设顶点编号0,1,2分别代表小明、小红、小刚
    // 用邻接矩阵来表示（后面会学），这里只是演示概念
    int n = 3; // 顶点数
    // 我们手动记录：0-1是朋友，1-2是朋友
    cout << "图有 " << n << " 个顶点" << endl;
    cout << "边: (0,1) 和 (1,2)" << endl;
    return 0;
}

理解图的基本概念后，我们就能用电脑来存储和处理复杂的关系网络了。图的用处很大，比如地图导航、社交网络、网页链接等都用到了图。

图的组成：顶点和边 —— 像拼积木一样

图就是“顶点”和“边”两个零件搭起来的。顶点代表“事物”，边代表事物之间的“关系”。

生活例子：

  • 全班同学是顶点，同桌关系是边（无向边）。
  • 电脑上的文件夹是顶点，文件夹之间的包含关系是边（有向边，A文件夹在B里面）。
  • 地铁站是顶点，地铁线路是边，如果两站之间来回都能坐车，就是无向边；如果某些线路是单程的（比如观光列车只往一个方向开），就是有向边。

在代码里，我们通常给顶点编号（0, 1, 2, ...），这样方便用数字表示。比如上面例子中，小明是0，小红是1，小刚是2，那么边就可以写成 (0,1) 和 (1,2)。

有向图与无向图 —— 单行道 vs 双行道

无向图：朋友关系

两个人互相认识，边没有方向。如果A和B是朋友，那么B和A也是朋友。存边时只需要存一对 (A, B)，谁先谁后都一样。

有向图：关注关系

比如微博上，你关注了某明星，但明星不一定关注你。这种关系有方向。这时我们需要记录方向：(A → B) 表示A关注B，与 (B → A) 完全不同。

代码小例子：
用一张表格（邻接矩阵）来存图，行列代表顶点，格子里的数字表示是否有边。

#include <iostream>
using namespace std;

int main() {
    // 顶点仍然是0,1,2三个
    int n = 3; // 顶点数
    
    // 无向图邻接矩阵：对称的
    int undirected[3][3] = {0}; // 初始化为0
    undirected[0][1] = 1; // 小明-小红是朋友
    undirected[1][0] = 1; // 对称也要写
    undirected[1][2] = 1; // 小红-小刚是朋友
    undirected[2][1] = 1; // 对称

    cout << "无向图邻接矩阵：" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << undirected[i][j] << " ";
        }
        cout << endl;
    }
    // 输出应该是：
    // 0 1 0
    // 1 0 1
    // 0 1 0

    // 有向图：比如0→1，1→2，但2→1不存在
    int directed[3][3] = {0};
    directed[0][1] = 1; // 0指向1
    directed[1][2] = 1; // 1指向2

    cout << "有向图邻接矩阵：" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << directed[i][j] << " ";
        }
        cout << endl;
    }
    // 输出：
    // 0 1 0
    // 0 0 1
    // 0 0 0
    return 0;
}

权重：给边加上“值”

很多实际问题中，边不仅仅是“有”或“没有”，还需要一个数值来表示代价、距离或时间。这个数值就叫权重（Weight）。

生活例子：

  • 地图导航里，每条路有长度（权重），让你知道哪条路更近。
  • 坐公交车，从A站到B站的车费不同，权重就是车费。
  • 朋友关系也可以有权重：比如两人认识的时间长短，或者亲密程度（用1~10打分）。

存储带权重的图时，邻接矩阵里放的不再是0或1，而是具体的数值（比如距离）。如果两个顶点之间没有边，我们通常放一个很大的数（比如 1000000）或者 -1 来表示。

#include <iostream>
using namespace std;

int main() {
    // 三个城市之间的距离（无向图，对称）
    int n = 3; // 城市数
    int INF = 1000000; // 表示无穷大（没有直接道路）
    int dist[3][3] = {
        {0, 10, INF},
        {10, 0, 20},
        {INF, 20, 0}
    };
    // 城市0到城市1距离10，城市1到城市2距离20，城市0到城市2没有直达路

    cout << "城市间距离矩阵：" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == INF)
                cout << "INF ";
            else
                cout << dist[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

注意：无向带权图的矩阵一定是对称的，有向带权图则不一定。

常见错误与注意事项

❌ 错误1：混淆有向和无向

写代码时，如果题目给的是有向图，你却按无向图存储（对称地填两边），会导致结果完全错误。比如计算单行道的路况，双向都能走就出错了。

解决方法：看清题目描述，是“双向道路”还是“单向边”。无向图存储时要对称填，有向图只能填一个方向。

❌ 错误2：顶点编号从0还是从1？

很多时候题目中顶点用1N编号，而代码里数组下标习惯从0开始。这时需要一个“转换”：要么存图时把顶点号减1，要么数组开大一点直接使用下标1N。

推荐做法：数组开成 int graph[N+1][N+1]，然后直接用顶点号作为下标，既方便又不易错。

❌ 错误3：权重太大或 INF 选择不当

如果权重范围是 0~1000，用 1000000 作为 INF 没问题。但如果要用加法（比如求最短路径），INF 不能太大（防止溢出），也不能太小（比如设 INF=10000，但实际权重总和可能超过10000，就会误判为有路）。通常用 int INF = 0x3f3f3f3f; 或 1e9。

❌ 错误4：忘记初始化

数组不初始化时，里面是垃圾值，必须手动赋0或INF。用 {0} 可以只初始化第一个元素，其余自动0。

完整示例：用邻接矩阵存储一个城市交通网络

假设有4个城市（编号1~4），道路信息如下（无向带权）：

  • 1--2 距离5
  • 1--3 距离3
  • 2--4 距离2
  • 3--4 距离1

现在要求：输出邻接矩阵，并查询从城市1到城市4是否直达？

#include <iostream>
using namespace std;

int main() {
    const int N = 5; // 城市编号1~4，下标0不用，所以大小设为5
    int graph[N][N] = {0}; // 全部初始化为0，表示无边
    
    // 录入边 (注意是无向图，对称存储)
    graph[1][2] = 5;
    graph[2][1] = 5;
    graph[1][3] = 3;
    graph[3][1] = 3;
    graph[2][4] = 2;
    graph[4][2] = 2;
    graph[3][4] = 1;
    graph[4][3] = 1;
    
    // 输出邻接矩阵
    cout << "   ";
    for (int i = 1; i <= 4; i++) cout << i << "  ";
    cout << endl;
    for (int i = 1; i <= 4; i++) {
        cout << i << " ";
        for (int j = 1; j <= 4; j++) {
            if (graph[i][j] == 0)
                cout << "0  ";
            else
                cout << graph[i][j] << "  ";
        }
        cout << endl;
    }
    
    // 查询城市1到城市4是否有直达路
    if (graph[1][4] != 0)
        cout << "城市1到城市4有直达路，距离=" << graph[1][4] << endl;
    else
        cout << "城市1到城市4没有直达路" << endl;
    
    return 0;
}

输出结果：

   1  2  3  4
1 0  5  3  0
2 5  0  0  2
3 3  0  0  1
4 0  2  1  0
城市1到城市4没有直达路

这个例子完整地演示了：定义顶点数组、初始化、存储边、输出矩阵、查询边的存在性。

相关指引

学会了图的定义和存储（邻接矩阵），接下来你可以学习：

  • 邻接表：当顶点很多、边很少时，用邻接矩阵浪费空间，邻接表更高效。
  • 图的遍历：深度优先搜索（DFS）和广度优先搜索（BFS），就像“走迷宫”和“体检排队”。
  • 最短路径：如何找到两个城市之间最短的路线？Dijkstra算法、Floyd算法。
  • 生成树：怎样用最少的道路连接所有城市？最小生成树（Kruskal、Prim）。

图是信息学竞赛的核心内容之一，好好掌握这些基础，后面会越学越有趣！

例题精讲

1单选题

一个无向图有6个顶点，所有顶点的度数之和为18，则该图有多少条边？

A6
B9
C12
D18
2判断题

具有5个顶点的有向完全图有25条边。

3填空题
以下函数用于计算无向图的边数，已知顶点数量为n，度数数组degree[]（长度为n），请填空。
int countEdges(int n, int degree[]) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += degree[i];
    }
    return ___;
}
4单选题

在无向图中，下列哪个说法是正确的？

A每个顶点的度数至少为1
B所有顶点的度数之和一定是偶数
C所有顶点的度数之和等于边数
D图必须包含环
5判断题

对于一个连通的无向图，其生成树是唯一确定的。