第1章：万物皆可“连”——从朋友圈到蜘蛛网，什么是图？

刷朋友圈时，你是否曾好奇：为什么好友A的动态下，总能看到好友B的点赞？这背后藏着怎样的“关系密码”？其实，你的朋友圈、地铁线路图、甚至游戏里的技能树，都是一张张看不见的“关系网”——在数学和计算机科学里，我们称之为“图”（Graph）。别被这个名字吓到，它可不是Excel里的图表，而是一种描述“事物之间连接”的超级工具。这一章，我们将一起揭开“图”的神秘面纱，你会发现：世界本来就是一个大网络，而学会用“图”的思维看世界，就像拿到了一副透视眼镜。

想象一下，你正站在一个巨大的蜘蛛网中央。每个结点上都挂着一颗露珠，代表一个人、一个地点或一个事物；而连接露珠的蛛丝，则代表它们之间的关系——可能是友谊、是距离、是依赖。这张网无处不在：你的微信好友列表是网，城市地铁线路是网，甚至你打游戏时解锁技能的顺序也是网。图，就是描述这种“连接结构”的语言。它简单到只有两个基本元素：节点（Node）和边（Edge）。节点就是网上的“点”，边就是连接点的“线”。但正是这简单的组合，却能描绘出从分子结构到全球互联网的复杂系统。

为什么我们需要“图”这种工具？因为世界本质上是关联的。一个人不是孤立的，他属于家庭、学校、兴趣小组；一个城市不是一堆建筑的集合，而是道路、地铁、公交编织的交通网；一首流行歌曲的走红，往往源于某个网红节点的推荐，然后像病毒一样扩散到整个网络。传统的列表或表格很难捕捉这种“关系”，而图却天生为此而生。它把“谁认识谁”“哪里连接哪里”“什么依赖什么”直观地画出来，让我们一眼看出谁是这个网络的核心，哪条路径最短，以及如何从一点影响到另一点。

你可能会想：这不就是网络图吗？没错！但“图”作为数学概念，比我们日常说的“网络”更严谨、更通用。在数学里，图论（Graph Theory）有超过280年的历史，最早是为了解决一个看似无关的趣味问题：柯尼斯堡的七座桥梁。18世纪的普鲁士城市柯尼斯堡（今俄罗斯加里宁格勒）被普列戈利亚河分成四块，河上有七座桥连接这些区域。市民们热衷一个谜题：能否找到一条路线，经过每座桥恰好一次，最终回到起点？数学家欧拉（Leonhard Euler）在1736年证明了这是不可能的，并由此创立了图论——他把陆地抽象为“节点”，桥抽象为“边”，问题转化为：在这个图中，是否存在一条经过每条边恰好一次的回路？这个抽象思维正是图的精髓：忽略具体形态，只关注连接关系。

从七桥问题到今天的社交网络分析，图论已经渗透到计算机科学、物理学、生物学、社会学等几乎所有领域。而图神经网络（Graph Neural Networks, GNNs）则是近年来人工智能的前沿，它让计算机学会“看懂”和“推理”这些图结构。但一切始于理解“图”本身。本章就是你的“图世界观”启蒙——不急着碰神经网络，我们先用手绘“关系地图”的游戏，搞懂节点、边、有向图无向图，然后猛然发现：原来我们每天生活的世界，本就是一张巨大的、活的网络。

---

节点与边：网络的最小积木

图的最基本构成单位是节点（Node，也称顶点 Vertex）和边（Edge）。节点代表实体——可以是一个人、一个城市、一个网页、一个基因；边代表实体之间的关系——可以是好友关系、地理距离、超链接、 biochemical 相互作用。用数学语言说，一个图 $G$ 定义为节点集 $V$ 和边集 $E$ 的二元组：$G = (V, E)$。每个边连接两个节点（在简单图中），如果边有方向，则称为有向边（Directed Edge），对应有向图（Directed Graph）；如果边无方向，则称为无向边（Undirected Edge），对应无向图（Undirected Graph）。

但定义是冰冷的，让我们用热腾腾的例子来感受。

社交网络：你的朋友圈就是一张图

打开微信，你的好友列表就是一组节点：你自己、小明、小红、小刚……节点之间的“好友关系”就是边。因为微信好友关系是相互的——如果你加了好友，对方也必须同意——所以这条边没有方向：你是小明的好友，小明也是你的好友。这对应一个无向图。我们可以用最简单的图示表示：

```mermaid graph LR 你 -- 好友 --> 小明 你 -- 好友 --> 小红 小明 -- 好友 --> 小刚 小红 -- 好友 --> 小刚 ```

在这个图中，节点是“你”“小明”“小红”“小刚”，边是“好友”关系。注意，边没有箭头，因为关系是对称的。如果你和小明是好友，那么小明和你也是好友，信息可以双向流动。

但社交网络不止一种。想想微博或 Twitter：你关注了某位博主，但对方不一定关注你。这里的“关注”关系是有方向的——你指向博主，但博主不一定指向你。这对应一个有向图。我们用箭头表示方向：

```mermaid graph TD 你 -->|关注| 博主A 博主A -->|关注| 大V 你 -.->|未关注| 大V ```

这里，边从关注者指向被关注者。你关注了博主A，博主A关注了大V，但你可能没关注大V，所以从你到大V没有边（或者用虚线表示潜在关系）。有向图能捕捉这种不对称性，对于分析信息传播、影响力至关重要：谁被很多人关注（入度高），谁关注很多人（出度高），完全是两回事。

动手时刻：拿出纸笔，画出你的“核心社交圈”。把你最亲密的5个朋友名字写在纸上，每两人之间如果是好友，就用直线连起来。你画出的正是一个无向图！数数看，你（中心节点）连接了几条边？朋友之间又有多少直接连接？这就是你的个人网络密度——如果朋友之间也都互相认识，这张图就很“稠密”；如果大家只通过你认识，这张图就很“星型”，你就是那个关键节点。

地铁线路：城市的地下神经网络

城市地铁系统是另一个经典的图例子。每个地铁站是一个节点，站点之间的轨道是边。但这里边可以有“权重”（Weight）——比如两站之间的距离、行驶时间、换乘次数。例如，北京地铁1号线，苹果园站到四惠东站之间有多个中间站，我们可以简化表示：

```mermaid graph LR 苹果园 --> 古城 古城 --> 八角游乐园 八角游乐园 --> 八宝山 %% ... 省略中间站 天安门西 --> 天安门东 天安门东 --> 王府井 王府井 --> 东单 ```

这是一个无向图吗？其实取决于具体问题。如果列车可以双向行驶，那么站A到站B和站B到站A是等价的，边是无向的。但如果考虑单行线路（比如某些轻轨或道路方向），边就有方向。更现实的是，我们常给边赋予权重：苹果园到古城的距离可能是2公里，古城到八角游乐园是1.5公里。这种带权图（Weighted Graph）能更精确地建模：求最短路径时，我们不是找边数最少的路径，而是找权重总和最小的路径——这正是高德地图、百度地图导航的核心算法之一（如Dijkstra算法）。

地铁图还是一个多层图（Multilayer Graph）的例子：不同线路是不同“层”，换乘站是跨层的连接节点。例如，西直门站是2号线、4号线和13号线的交汇点，它同时属于三个线路层，并在层间有边。这种多层结构让城市交通变得高效，也让我们在分析时能考虑线路切换的成本。

游戏技能树：有向无环图的完美范例

如果你玩过《暗黑破坏神》《魔兽世界》或《原神》这类角色扮演游戏，一定对“技能树”不陌生。技能树是一个典型的有向图，而且通常是一个有向无环图（Directed Acyclic Graph, DAG）——因为技能依赖关系不能出现循环：你不能既需要A才能学B，又需要B才能学A，那将陷入死锁。

以《原神》的元素反应技能为例：假设你想解锁“超载”技能，可能需要先解锁“火元素基础”和“雷元素基础”。这形成两条有向边：

```mermaid graph TD 火元素基础 --> 超载 雷元素基础 --> 超载 火元素基础 --> 炎爆 雷元素基础 --> 雷束 ```

节点是技能，边表示“前置依赖”。箭头从基础技能指向高级技能，表示“学会前者才能解锁后者”。这种图结构让游戏设计师能控制角色成长节奏：玩家必须按顺序投入资源，不能跳过基础直接学高级。同时，技能树往往是一个DAG，确保没有循环依赖，否则游戏逻辑会崩溃。

有趣的是，技能树图还常常是树状结构（Tree）的一种变体——一种特殊的有向无环图，其中每个节点（除了根节点）只有一个父节点。例如，“火元素基础”可能是“元素掌控”的子技能，而“元素掌控”又是“角色等级1”的子技能，形成一条链。但有时技能也有多路径，比如“火元素基础”可以走向“炎爆”或“火盾”，这就有了分支，但依然无环。

从具体到抽象：图的通用语言

现在，我们抽象出图的本质：

• **节点**：表示实体或对象。
• **边**：表示实体间的关系或交互。
• **无向边**：关系对称（如好友、合作、距离）。
• **有向边**：关系不对称（如关注、引用、依赖）。
• **权重**：边的属性，表示强度、成本、概率等（如亲密度分数、地铁行驶时间、技能学习消耗的点数）。
• **自环**（Self-loop）：节点连接到自身（如“自己引用自己”在某些引文网络中可能，但通常简单图排除）。
• **多重边**（Multiedge）：同一对节点间有多条边（如两人合作多篇论文，或地铁有快慢车不同线路）。

图可以非常简单，比如三个节点的三角形无向图；也可以极其庞大，比如Facebook的社交图有数十亿节点和万亿条边。但无论规模，核心思想一致：用连接定义结构。

---

有向与无向：关系的方向性之谜

方向性是图最核心的区分之一。为什么有的关系需要方向，有的不需要？这取决于关系本身的语义。

无向图：双向对称的关系

在无向图中，边没有箭头，表示关系是相互的、对称的。典型例子：

• **好友关系**：在Facebook或微信中，好友是双向确认的。
• **合作网络**：两位作者合著一篇论文，合作是相互的。
• **地理邻接**：两个国家接壤，这种接壤关系是对称的。
• ** undirected 的物理连接**：一根电线连接两个电器，电流可双向流动（尽管实际有方向，但连接本身无向）。

无向图可以用邻接矩阵（Adjacency Matrix）表示：一个 $n \times n$ 的矩阵 $A$，其中 $A_{ij} = 1$ 表示节点 $i$ 和节点 $j$ 之间有边，否则为0。由于对称性，矩阵关于对角线对称。例如，四个节点的无向图：

节点：1,2,3,4 边：(1,2), (1,3), (2,4)

邻接矩阵： ``` 1 2 3 4 1 [0 1 1 0] 2 [1 0 0 1] 3 [1 0 0 0] 4 [0 1 0 0] ``` 注意 $A_{12}=A_{21}=1$，体现对称。

无向图也可以用邻接表（Adjacency List）表示：每个节点关联一个列表，列出所有邻居。例如： ``` 1: [2, 3] 2: [1, 4] 3: [1] 4: [2] ``` 邻接表更节省空间，尤其对稀疏图（边数远小于 $n^2$）。

有向图：单向流动的关系

有向图中，边有箭头，表示关系单向。典型例子：

• **关注/粉丝**：Twitter、微博、Instagram 的“关注”关系。
• **引用网络**：学术论文A引用了论文B，形成从A到B的有向边。
• **网页链接**：网页A超链接到网页B，形成从A到B的有向边（整个互联网就是一张有向图）。
• **依赖关系**：技能树、项目任务调度（先完成A才能开始B）、食物链（吃与被吃）。
• **交通流**：单行道、航班航线（从城市A到城市B的航班）。

有向图的邻接矩阵不再对称：$A_{ij}=1$ 表示从 $i$ 指向 $j$ 的边，但 $A_{ji}$ 可能为0。例如，一个三人关注网络：小明关注小红，小红关注小刚，小刚未关注小明。

邻接矩阵： ``` 小明 小红 小刚 小明 [0 1 0] 小红 [0 0 1] 小刚 [0 0 0] ``` 这里，小明→小红有边（矩阵[小明,小红]=1），但小红→小明无边（矩阵[小红,小明]=0）。

有向图还可以有双向边（Two-way edge）：如果小明和小红互相关注，则存在两条有向边：小明→小红和小红→小明。这等价于无向边，但在有向图表示中需要两条边。

混合图：现实世界的复杂性

现实网络常混合有向和无向边。例如，一个社交平台可能既有“好友”无向边（双向确认），也有“关注”有向边（单向）。在建模时，我们可以： 1. 统一用有向图表示：将无向边替换为一对反向的有向边。 2. 使用混合图（Mixed Graph）：明确允许边有向或无向。 3. 根据问题选择合适的图类型：如果研究信息传播，关注关系（有向）更重要；如果研究社区发现，好友关系（无向）可能更相关。

有向无环图（DAG）：没有循环的依赖

如果图中所有边都有方向，且不存在从一个节点出发沿箭头走最终回到该节点的路径，这就是有向无环图（DAG）。DAG 在计算机科学中极为重要：

• **编译依赖**：源文件A依赖头文件B，编译顺序必须拓扑排序。
• **任务调度**：项目任务有前后置条件，DAG表示依赖，关键路径算法确定最短工期。
• **版本历史**：Git提交历史是DAG，每个提交有父提交，但不能循环。
• **技能树**：如前所述，通常设计为DAG以避免死锁。
• **引文网络**：论文引用形成DAG，因为不可能出现A引用B且B引用A的循环（除非自引，但自环通常忽略）。

DAG 的一个重要性质是拓扑排序（Topological Sorting）：可以将所有节点线性排序，使得每条有向边从前指向后。例如，技能树可以按解锁顺序排列；编译顺序可以据此确定。拓扑排序的存在当且仅当图是无环的。

方向性如何改变网络性质？

方向性彻底改变了图的拓扑性质和动态过程：

• **连通性**：

方向性彻底改变了图的拓扑性质和动态过程：

• **连通性**：在无向图中，连通性是对称的——如果A能到B，则B也能到A。但在有向图中，连通性变得复杂：可能存在从A到B的路径，但没有从B到A的路径。这种**弱连通**（忽略方向后连通）和**强连通**（考虑方向后每对节点相互可达）的区分，对于分析信息传播至关重要。例如，在微博中，你可能能通过关注链看到大V的动态（有路径），但大V不一定能看到你的（无返回路径），所以网络不是强连通的。

• **中心性度量**：有向图中，节点的“重要性”有多种定义。**入度**（In-degree）指指向该节点的边数（如粉丝数），**出度**（Out-degree）指该节点指出的边数（如关注数）。一个节点入度高说明它被很多人关注（影响力大），出度高说明它关注很多人（信息采集者）。无向图只有度（Degree），没有方向区分。

• **动态过程**：信息、病毒或影响力的传播在有向和无向图中表现不同。在无向好友网络中，谣言可能快速对称扩散；在有向关注网络中，信息通常从高入度节点流向出度节点，形成“广播式”传播，难以反向。

权重图：关系也有“分量”

现实中的关系往往不是简单的“有”或“无”，而是有强度、成本或概率的。这就是权重（Weight）的用武之地。带权图（Weighted Graph）为每条边赋予一个数值，表示关系的属性。

例子1：地图导航 高德地图中，两点间的路径不是单纯看经过几个路口，而是计算总时间或距离。每条道路（边）有权重：高速公路权重低（时间短），拥堵街道权重高（耗时长）。最短路径算法（如Dijkstra）就是在带权图中找权重和最小的路径。 ```mermaid graph LR A[家] --|权重: 10分钟| B[地铁站] B --|权重: 20分钟| C[学校] A --|权重: 35分钟| D[公交站] D --|权重: 25分钟| C ``` 这里，从家到学校，经地铁站路径总权重30分钟，经公交站60分钟，所以最优路径是A→B→C。

例子2：游戏技能树 学习技能不仅需要前置，还需要消耗资源：技能点、金币、时间。这些可以表示为权重。例如，“火球术”需要前置“火元素基础”（有向边），同时消耗10点魔力（权重）。如果权重过高，玩家可能选择替代路径。

例子3：社交亲密度 在微信中，你和不同好友的聊天频率、点赞互动可以量化为“亲密度权重”。权重高的边代表 stronger relationship。分析带权社交图，能发现你的“核心朋友圈”不仅是常联系的人，还可能包括偶尔但深度交流的朋友。

权重使图更精细，但也增加计算复杂度。在后续GNN中，权重会作为边特征输入，让模型理解关系的强弱。

自环与多重边：图的“特殊用法”

大多数简单图假设没有自环（Self-loop，节点连接自身）和多重边（Multiedge，同一对节点间多条边）。但现实有时需要它们。

• **自环**：表示节点与自身的关系。在技能树中，可能表示“重复学习同一技能以升级”；在社交网络中，可能表示“自我反思”或“自引用”（如论文自引）；在分子图中，可能表示化学键的环状结构。但通常，简单图排除自环以简化理论。

• **多重边**：两个节点间存在多种关系。例如，两位作者合作了多篇论文，每篇论文对应一条边，形成多重边。地铁系统中，两个站点间可能有多种线路（如北京地铁2号线和13号线都连接东直门和西直门？实际不同，但假设有重复线路）。多重边可以用**边标签**（Edge Label）区分类型，如“合作论文1”“合作论文2”。

在数学定义中，简单图（Simple Graph）既无自环也无多重边；多重图（Multigraph）允许多重边；伪图（Pseudograph）允许自环和多重边。选择哪种图取决于建模需求。

---

图的表示法：如何用计算机“画”出一张网

图不仅要能画出来，还要能被计算机存储和处理。主要有三种表示方法，各有优劣。

1. 邻接矩阵（Adjacency Matrix）

一个 $n \times n$ 的矩阵 $A$，其中 $A_{ij}$ 表示节点 $i$ 到节点 $j$ 的边。对于无向图，矩阵对称；对于有向图，不一定对称。如果边有权重，$A_{ij}$ 存储权重值；如果没有边，通常存储0或无穷大（表示不可达）。

优点：

• 检查任意两点间是否有边：$O(1)$ 时间。
• 适合稠密图（边数接近 $n^2$）。
• 矩阵运算方便（如计算路径数：$A^k$ 的 $ij$ 元素表示从 $i$ 到 $j$ 长度为 $k$ 的路径数）。

缺点：

• 空间复杂度 $O(n^2)$，对稀疏图（边数远