图的定义与种类
困难8用点和线搭出你的关系网：认识图这种数据结构
小朋友，你有没有玩过“连点成线”的游戏？在纸上画几个点，然后用线把其中一些点连起来，这就组成了一张“图”。在计算机里，图也是一种存储数据之间关系的方法。它像一张城市地图，能表示事物之间各种连接。每个点我们叫它顶点（Vertex），每条线叫边（Edge）。
今天我们要一起认识图的几种常见类型，并且用 C++ 代码把图“画”到电脑里。
图的种类：无向图、有向图、带权图
1. 无向图——朋友关系
无向图的边没有方向，就像你和你的好朋友：如果小明和小红是朋友，那么这条线就没有箭头，两个人可以互相找到对方。你认识我，我也认识你。
生活中的例子：你和同桌一起分享零食，只要你们是朋友，他给你糖，你给他饼干，这条“友谊边”就是双向的。
用代码怎么表示？ 我们可以用一个表格（叫邻接矩阵）来记录每对顶点之间有没有边。比如有 5 个顶点（编号 0 到 4），如果顶点 0 和顶点 1 是朋友，我们就在表格的第 0 行第 1 列写 1，同时在第 1 行第 0 列也写 1——因为无向边是双向的。
2. 有向图——单向车道
有向图的边有方向，就像一条单行道：箭头从 A 指向 B，表示只能从 A 走到 B，B 不能直接走到 A。如果 A 给 B 写了一封信，B 不回信，这就是有向关系。
生活中的例子：你在班级里关注了一个明星同学，你经常看他，但他不一定看你。这个“关注”就是单向的。再比如，你向妈妈要零花钱，钱只能从妈妈流向你，不能反过来。
表示方式：邻接矩阵里，如果有一条从 i 到 j 的有向边，我们只在 graph[i][j] 处写 1，graph[j][i] 不写（还是 0）。
3. 带权图——地图上的距离
带权图就是在每条边上加一个数字，这个数字叫做权值。就像地图上标注的城市之间距离：北京到上海 1000 公里，北京到天津 150 公里。带权图可以表示距离、时间、花费、甚至“赢得游戏的分数”。
生活中的例子：周末你想去游乐园，从家到公交站 200 米，从公交站到游乐园 3 公里，这些数字就是边的权值。你想找一条最短的路，就用到带权图。
表示方式：邻接矩阵里，原来放 1 的位置，现在换成具体的权值。如果两个顶点之间没有直接的路，我们就放一个很大的数（比如 1000000）或者 0（取决于约定）。
认识邻接矩阵：把图装进二维数组
刚才提到的“表格”就是邻接矩阵。它是一个二维数组，行号表示起点，列号表示终点。对于有 n 个顶点的图，邻接矩阵是 n×n 的。
- 对于无向图：如果顶点 i 和 j 有边，则
graph[i][j] = graph[j][i] = 1（或权值）。 - 对于有向图：如果 i → j 有边，则
graph[i][j] = 1，graph[j][i]通常为 0（除非也有反方向的边）。 - 对于带权图：把 1 换成具体数字，没有边的地方放 0 或者一个很大的数。
一个小例子：无向图的朋友圈
假设超级英雄有 4 个朋友：蜘蛛侠（0）、钢铁侠（1）、美国队长（2）、绿巨人（3）。他们之间的关系如下：
- 蜘蛛侠和钢铁侠是朋友
- 钢铁侠和美国队长是朋友
- 美国队长和绿巨人是朋友
用代码表示：
#include <iostream>
using namespace std;
int main() {
// 顶点个数为4
int n = 4;
// 创建4x4的邻接矩阵，全部初始化为0（表示还没有边）
int graph[4][4] = {0};
// 添加朋友关系：每个无向边要填两个位置
graph[0][1] = 1; // 蜘蛛侠-钢铁侠
graph[1][0] = 1;
graph[1][2] = 1; // 钢铁侠-美队
graph[2][1] = 1;
graph[2][3] = 1; // 美队-绿巨人
graph[3][2] = 1;
// 输出整个矩阵
cout << "图（朋友关系）的邻接矩阵：" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << graph[i][j] << " ";
}
cout << endl; // 每输出一行换行
}
return 0;
}
运行结果会显示一个 4×4 的矩阵：
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
第 0 行第 1 列是 1，表示蜘蛛侠和钢铁侠有边；第 1 行第 2 列是 1，表示钢铁侠和美队有边……注意到矩阵关于对角线对称（graph[i][j] == graph[j][i]），这正是无向图的特点。
新手容易踩的坑
坑1：无向图只填一个方向
有同学添加无向边时，只写了 graph[0][1] = 1，忘记写 graph[1][0] = 1，结果图变得有方向了，程序以为只能从 0 到 1，不能反向。这样后期判断两个人是不是朋友就会出错。
正确做法：添无向边，记得两个位置都赋值。
坑2：顶点编号从 1 开始用，下标却从 0 开始
很多同学在生活中数数从 1 开始，但 C++ 数组下标从 0 开始。如果你有 5 个顶点，编号写成 1,2,3,4,5，但数组下标只能用到 0~4。容易造成数组越界。
建议：要么让顶点编号和数组下标一致（0~n-1），要么定义大小为 n+1 的数组，放弃第 0 行和第 0 列。
坑3：忘记初始化矩阵
C++ 中如果定义 int graph[5][5]; 而不初始化，数组里是随机值，不是 0。这样添加边之前，矩阵里乱七八糟的数字会干扰判断。
正确做法：用 int graph[5][5] = {0}; 把所有元素都初始化成 0。
坑4：带权图里没有边的位置用 0 还是大数？
如果用 0 表示没有边，权值也可能是 0（比如免费公交），就会混淆。通常我们用一个大数（如 1000000）或 -1 表示“不可达”。
完整示例：混合展示三种图
下面一个代码示例，创建了一个有向图、一个无向图、一个带权图，简单验证你掌握的概念。为了让代码更清晰，我们用类（或者简单函数）封装，不过这里还是用直接的方式，方便理解。
#include <iostream>
using namespace std;
int main() {
// ========== 1. 无向图示例：4个城市的公路 ==========
cout << "=== 无向图：城市公路（双向） ===" << endl;
int n = 4; // 城市数量
int undirected[4][4] = {0}; // 邻接矩阵，初始为0
// 城市0-1之间有路，城市1-2之间有路，城市2-3之间有路
undirected[0][1] = 1;
undirected[1][0] = 1;
undirected[1][2] = 1;
undirected[2][1] = 1;
undirected[2][3] = 1;
undirected[3][2] = 1;
// 输出矩阵
cout << "邻接矩阵：" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << undirected[i][j] << " ";
}
cout << endl;
}
// ========== 2. 有向图示例：课程依赖关系 ==========
cout << "\n=== 有向图：课程先修关系 ===" << endl;
int n2 = 3; // 3门课：0-数学, 1-物理, 2-化学
int directed[3][3] = {0};
// 数学是物理的先修课（0→1），物理是化学的先修课（1→2）
directed[0][1] = 1; // 从0到1有一条有向边
directed[1][2] = 1;
cout << "邻接矩阵：" << endl;
for (int i = 0; i < n2; i++) {
for (int j = 0; j < n2; j++) {
cout << directed[i][j] << " ";
}
cout << endl;
}
cout << "注意：矩阵不是对称的，因为是有向图。" << endl;
// ========== 3. 带权图示例：两两之间距离 ==========
cout << "\n=== 带权图：三个城市之间的距离 ===" << endl;
int n3 = 3; // 三个城市：0,1,2
int weighted[3][3] = {0};
weighted[0][1] = 100; // 城市0到城市1距离100公里
weighted[1][0] = 100; // 无向，所以双向权值一样
weighted[1][2] = 200;
weighted[2][1] = 200;
weighted[0][2] = 250; // 城市0直接到城市2距离250公里
weighted[2][0] = 250;
cout << "邻接矩阵（权值）：" << endl;
for (int i = 0; i < n3; i++) {
for (int j = 0; j < n3; j++) {
cout << weighted[i][j] << " ";
}
cout << endl;
}
return 0;
}
输出结果：
=== 无向图：城市公路（双向） ===
邻接矩阵：
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
=== 有向图：课程先修关系 ===
邻接矩阵：
0 1 0
0 0 1
0 0 0
注意：矩阵不是对称的，因为是有向图。
=== 带权图：三个城市之间的距离 ===
邻接矩阵（权值）：
0 100 250
100 0 200
250 200 0
你看，三种图用邻接矩阵表示都非常清晰。
小小思考
-
如果现在要表示一个朋友圈软件的好友关系（比如你关注了A，A也关注了你，但A和B之间没有关注），应该用无向图还是有向图？
- 提示：好友关系是双向的，所以用无向图更简单。但如果是“关注”关系（我关注你，你不一定要关注我），那就得用有向图。
-
地铁线路图上，站与站之间有长度（多少米），这个图是哪种类型？
- 提示：地铁线路是双向的，而且有距离，所以是无向带权图。
相关指引
学会了用邻接矩阵表示图，接下来你可以探索：
- 图的遍历（深度优先搜索 DFS、广度优先搜索 BFS）——怎么在图中走一遍，访问所有顶点。
- 图的存储方式：除了邻接矩阵，还有邻接表（适合稀疏图，省内存）。
- 最短路径算法（比如 Dijkstra 算法）：如何找到从一个城市到另一个城市的最短路。
在七级到八级的编程学习中，图是一个非常重要的工具，它能帮你解决很多现实中的关系问题，比如社交网络、交通规划、游戏地图寻路。继续加油，你一定能掌握它！
例题精讲
一个有10个顶点的无向完全图有多少条边？
下列关于图的说法中，哪一个是错误的？
在有向图中，所有顶点的入度之和等于出度之和。
一个具有 n 个顶点的完全有向图（不考虑自环）的边数为 n×(n-1)。
以下代码使用邻接矩阵统计无向图中顶点 v 的度数（假设无向图没有自环，顶点编号从0到n-1）。请将循环条件补充完整。
int graph[100][100]; // 邻接矩阵
int n; // 顶点个数
int v; // 待统计度数的顶点
int degree = 0;
for(int i = 0; i < ___; i++) {
if(graph[v][i] == 1) degree++;
}