从导航到代码：带权图如何撑起数据结构中的「距离美学」

当你打开导航 APP，选择 “最短距离” 模式时，背后其实藏着一种关键的数据结构 ——带权图。不同于只记录 “是否相连” 的普通图，带权图给每条边都加上了 “权重”，可能是距离、时间、成本，正是这种 “量化关系”，让它成为解决现实问题的核心工具。今天我们就从原理到代码，拆解带权图的奥秘。

一、带权图：不止 “相连”，更要 “算清楚”

先举个简单的例子：假设你要从 A 地到 B 地，有两条路可选 —— 一条直线距离 5 公里，一条绕路 10 公里。如果用普通图表示，只能看出 “A 和 B 有两条连接边”；但带权图会给这两条边分别标注 “5” 和 “10”，让我们能直观判断 “选哪条更优”。

从定义上看，带权图由 “顶点” 和 “带权边” 组成：

• 顶点：对应现实中的节点（比如路口、站点）；
• 带权边：连接两个顶点的 “关系”，且附带一个数值（权重），代表两者之间的量化关联。

它的应用场景远比你想象的广：物流行业计算运输成本、社交网络计算好友亲密度、电路设计计算电阻值，本质上都是在操作带权图。

二、用邻接矩阵存储带权图：代码里的 “关系表”

想要用代码实现带权图，首先要解决 “如何存储” 的问题。最经典的方式就是邻接矩阵—— 用一个二维数组记录顶点之间的权重，让复杂的 “图关系” 变成清晰的 “表格”。

我们直接结合一段可运行的 C 语言代码来理解（代码改编自实用的邻接矩阵实现，已优化可读性）：

#include<stdio.h>

#define Max 0x7fffffff // 用极大值表示“无连接”

typedef char vertaxType; // 顶点类型（这里用字符表示，比如'0'、'1'）

typedef int edgeType; // 边的类型（权重是整数，比如距离、成本）

#define maxsize 100 // 最大顶点数

// 带权图的邻接矩阵结构体

typedef struct mat_grph {

vertaxType ver[maxsize]; // 存储顶点的数组

edgeType arc[maxsize][maxsize]; // 存储边的权重（邻接矩阵核心）

int ver_num; // 实际顶点数

int arc_num; // 实际边数

} mat_grph;

这段代码的关键在于arc这个二维数组：

• 若arc[i][j] = 0：表示顶点 i 和自身相连（权重为 0，因为自己到自己没有距离）；
• 若arc[i][j] = Max（极大值）：表示顶点 i 和 j 不直接相连；
• 若arc[i][j] = 5（具体数值）：表示顶点 i 到 j 的边，权重为 5。

三、手把手实现带权图：从初始化到输出

光有结构体还不够，我们需要通过代码给带权图 “填充数据”，再让它 “展示自己”。下面分两步拆解：

1. 初始化带权图：给 “关系表” 填内容

初始化的核心是 “确定顶点、设置权重”。比如我们要创建一个 4 个顶点、5 条带权边的图，代码逻辑如下：

// 初始化带权图

void init_grph(mat_grph* G) {

// 1. 确定顶点数和边数

G->ver_num = 4; // 4个顶点（编号0-3，用'0'/'1'/'2'/'3'表示）

G->arc_num = 5; // 5条带权边

// 2. 给顶点命名（这里简化为'0'到'3'）

for (int k = 0; k < G->ver_num; k++) {

G->ver[k] = '0' + k;

}

// 3. 初始化邻接矩阵：先设为“无连接”（Max），自身连接设为0

for (int i = 0; i < G->ver_num; i++) {

for (int j = 0; j < G->ver_num; j++) {

G->arc[i][j] = Max; // 默认“不相连”

if (i == j) {

G->arc[i][j] = 0; // 自身到自身权重为0

}

}

}

// 4. 手动添加带权边（关键步骤！）

G->arc[1][0] = 5; // 顶点1到0，权重5

G->arc[1][2] = 2; // 顶点1到2，权重2

G->arc[2][1] = 4; // 顶点2到1，权重4（注意：边可能有方向，这里是有向带权图）

G->arc[2][0] = 6; // 顶点2到0，权重6

G->arc[0][3] = 3; // 顶点0到3，权重3

}

这里有个细节：我们用Max（0x7fffffff，即 int 类型的最大值）表示 “无连接”，比直接用 0 更合理 —— 如果用 0 表示无连接，会和 “自身连接的权重 0” 混淆，而极大值在后续计算中（比如求最短路径）也更容易判断和处理。

2. 输出带权图：让 “关系表” 看得见

初始化后，我们需要一个函数把邻接矩阵打印出来，验证是否正确。代码如下：

// 输出带权图的邻接矩阵

void print_grph(mat_grph G) {

printf("带权图邻接矩阵（Max表示无连接，数字表示权重）：\n");

// 先打印顶点名（方便对应）

for (int k = 0; k < G.ver_num; k++) {

printf(" %c", G.ver[k]);

}

printf("\n");

// 打印邻接矩阵内容

for (int i = 0; i < G.ver_num; i++) {

printf("%c ", G.ver[i]); // 行对应的顶点

for (int j = 0; j < G.ver_num; j++) {

if (G.arc[i][j] == Max) {

printf("Max ");

} else {

printf("%-5d", G.arc[i][j]); // 左对齐，更整齐

}

}

printf("\n");

}

}

运行这段代码后，输出结果会是这样：

带权图邻接矩阵（Max表示无连接，数字表示权重）：

0 1 2 3

0 0 Max Max 3

1 5 0 2 Max

2 6 4 0 Max

3 Max Max Max 0

一眼就能看出：顶点 0 到 3 的权重是 3，顶点 1 到 0 的权重是 5，顶点 2 到 1 的权重是 4…… 带权图的 “量化关系” 清晰明了。

四、带权图的核心价值：从 “存” 到 “用” 的跨越

看到这里，你可能会问：“存储和打印只是基础，带权图真正的价值在哪？” 答案是 “基于权重的计算”。比如经典的迪杰斯特拉算法，就是通过带权图的邻接矩阵，找到 “从一个顶点到其他所有顶点的最短路径”—— 这正是导航 APP “最短距离” 功能的核心逻辑。

举个例子，从顶点 1 出发，通过邻接矩阵能算出：

• 到顶点 0 的最短路径：直接走 1→0（权重 5）；
• 到顶点 2 的最短路径：直接走 1→2（权重 2）；
• 到顶点 3 的最短路径：1→0→3（权重 5+3=8）。

这些计算都依赖于带权图中 “边的权重信息”，如果没有权重，我们根本无法判断 “哪条路更近”。

结语：带权图，让数据结构 “落地” 现实

从代码里的邻接矩阵，到生活中的导航路线，带权图的本质是 “给关系加量化标准”。它不像普通图那样只做 “有无判断”，而是用权重让数据结构更贴近现实需求 —— 毕竟在真实世界里，我们不仅要知道 “能到哪”，更要知道 “怎么到更优”。

如果你想进一步探索，可以尝试在今天的代码基础上实现迪杰斯特拉算法，或者用邻接表（另一种带权图存储方式）改写代码。数据结构的魅力，就在于从 “理解” 到 “改造” 的过程，而带权图，正是开启这个过程的绝佳起点。