神奇的世界，到处都是「图」

第 1 章：神奇的世界，到处都是「图」

想象这样一个场景：今天早上你睁开眼睛，看到了熟悉的天花板。你从床上爬起来，走进卫生间洗漱，然后走到厨房吃早餐。吃完早餐后，你背上书包，和爸爸妈妈说再见，走出家门去上学。在路上，你可能会遇到同学小明，你们一起走向学校。来到教室后，你找到了自己的座位，打开书包准备开始新一天的学习。

你有没有想过，在这些看似普通的日常活动中，隐藏着一种神奇的结构？这种结构把世间万物联系在一起，就像一张看不见的大网。而今天，我们要一起去探索这张神秘的大网——「图」。

「图」是什么？听到这个问题，你可能会想到图画、地图、照片。但在这里，我们要认识的「图」可不是你用蜡笔在纸上画的那些可爱的图案。在数学和计算机科学的世界里，「图」是一种用来描述事物之间关系的强大工具。它的英文名字叫 Graph，中文翻译为「图」或者「图形」。别小看这个简单的名字，它可是计算机科学中最重要的概念之一呢！

让我们先来做一个小小的思想实验。假设你现在要给班上的同学介绍你的好朋友，你可能会说：「小明是我的好朋友，我们经常一起放学回家。」或者「小红是我的同桌，我们坐前后桌。」在这些描述中，你其实已经在无意识地使用「图」的思想了。你把同学看作一个个「点」，把同学之间的关系用「线」连接起来。这就是「图」最基本的形态：由「节点」和「边」组成的神奇结构。

1.1 从朋友圈说起：初识节点与边

让我们更仔细地观察一下你刚才描述的那个「同学关系网络」。如果把它画成一幅图，会是什么样子呢？

首先，你需要把每一个同学用一个「点」来表示。在图论中，我们把这些点叫做「节点」（Vertex，复数形式是 Vertices）。你可以把节点想象成一张张可爱的便利贴，每一张便利贴上写着一个同学的名字，然后把它们贴在墙上。如果你们班有30个同学，你就需要30张便利贴。

接下来，你需要表示同学之间的关系。对于你和小明的友谊，你可以在写着「你」的便利贴和写着「小明」的便利贴之间画一条线。这条线就叫做「边」（Edge）。边表示了两个节点之间的联系或关系。

这样一来，你就把一个抽象的「同学关系网络」变成了一幅直观的「关系图」！这幅图看起来可能有点像下面这个样子：

```mermaid graph TD A["🧒 你"] --- B["🧒 小明"] A --- C["🧒 小红"] A --- D["🧒 小华"] B --- C B --- E["🧒 小刚"] C --- D C --- E D --- F["🧒 小丽"] E --- F ```

看，在这幅图中：

• 每一个小头像代表一个「节点」，表示班级里的一个同学
• 连接两个头像的线条代表「边」，表示这两个同学是好朋友关系

这就是一个最简单的「图」！现在你应该对节点和边有了初步的认识。节点就像是宇宙中的星球，每一个都是独立的存在；边就像星球之间的引力，把相关的星球联系在一起。没有边，节点就是孤立的一个个点；没有节点，边就失去了依附的主体。节点和边相互依存，共同构成了「图」这个整体。

1.2 身边的图：发现隐藏的关系网

现在你已经知道了图的基本构成，那么让我们一起来找找生活中还有哪些「图」的存在。我敢保证，一旦你学会了用「图」的眼光看世界，你会发现它无处不在！

1.2.1 家族谱系图：血脉相连的网络

你一定见过家谱图吧？也许你家里就挂着一幅长长的家族谱系图，上面记录着你爷爷、奶奶、爸爸、妈妈，还有叔叔阿姨、堂兄弟姐妹们的名字。恭喜你，那就是一个典型的「图」！

在家族谱系图中：

• **节点** 代表家族中的每一个人
• **边** 代表血缘关系，比如「父子」「母子」「兄弟」等

家族谱系图有一个非常有趣的特点：它的边是有「方向」的。什么意思呢？想象一下，你和你爸爸之间的关系。你是你爸爸的儿子（或者女儿），但你爸爸可不是你的儿子。这种关系是有明确方向的——你从爸爸那里来，但你爸爸不是从你那里来的。这种有方向的边叫做「有向边」，用带箭头的线表示。

```mermaid graph TB A["👴 爷爷"] --> B["👨 爸爸"] A --> C["👨 叔叔"] B --> D["🧒 你"] B --> E["🧒 姐姐"] C --> F["🧒 堂弟"] D --> G["👶 你的儿子"] ```

在这幅家族图中，箭头从长辈指向晚辈，清楚地展示了血脉的传承关系。你可以从这幅图中一眼看出：爷爷是爸爸和叔叔的父亲，爸爸是你的父亲，而你是你儿子的父亲。这就是有向图的强大之处——它能够精确地表示关系中的方向性。

1.2.2 城市交通图：四通八达的脉络

第二个例子是你每天都会接触到的——城市交通图。当你坐车去公园玩，或者让爸爸妈妈开车带你去外婆家的时候，你们都需要遵循交通网络的指引。

在城市交通网络中：

• **节点** 代表交叉路口、地铁站、公交站，或者重要的地点（比如学校、商场、公园）
• **边** 代表连接这些地点的道路，可以是马路、地铁线路、公交线路等

想象一下你从家去学校的路线。你家门前的路口是一个节点，学校门口的路口是另一个节点，连接它们的那条马路就是一条边。如果你家和学校之间有多条路可以走，那么这些不同的路线就构成了一个复杂的「交通图」。

```mermaid graph LR A["🏠 家"] -->|"路线1: 5分钟"| B["🚶 十字路口"] A -->|"路线2: 8分钟"| C["🏪 便利店"] B -->|"直达: 10分钟"| D["🏫 学校"] C -->|"换乘: 5分钟"| B B -->|"步行: 3分钟"| D ```

这个交通图不仅仅展示了你家到学校的连接关系，还告诉你每条路线需要花费的时间。没错！在真实世界的图中，边往往还带有「权重」——用来表示距离、时间、花费等各种度量。就像上面的例子中，边的权重就是走这条路线需要花费的时间。这种带有权重的图叫做「加权图」，它能够更精确地描述现实世界中的复杂关系。

1.2.3 互联网：看不见的数字海洋

你知道吗？当你用电脑或者手机浏览网页的时候，你其实正在一个巨大的「图」中遨游！这个图叫做「万维网」（World Wide Web），它是迄今为止人类创造的最复杂的图之一。

在万维网中：

• **节点** 代表每一个网页
• **边** 代表从一个网页到另一个网页的链接

当你点击一个网页上的链接，跳转到另一个网页的时候，你其实就是在图的节点之间穿梭。每当你发布一条微博或者微信朋友圈，你的账号和其他人的账号之间就形成了新的「边」。社交网络上的好友关系、关注关系、点赞关系，都是通过「图」来存储和管理的。

据估计，全球互联网拥有超过17亿个网站，每一个网站就是一个节点。它们之间通过超链接相互连接，构成了一个庞大的、有史以来最复杂的信息网络。想象一下这个数字有多大——如果把每一个网站都比喻成一颗沙子，那么整个互联网就像一片无边无际的沙滩！

1.2.4 更多有趣的例子

除了上面这几个例子，「图」的身影还出现在很多你意想不到的地方：

生物网络：在你身体内部，有一张由神经元组成的巨大网络。当你想要抬手拿一本书的时候，大脑发出的指令就是通过神经网络传递到手臂的肌肉的。在这个网络中，每一个神经元是一个节点，而神经元之间的信号传递就是边。在生物学中，科学家们还用「图」来研究蛋白质之间的相互作用、基因之间的调控关系等等。

电力网络：你家用的电是从发电厂通过电网输送到千家万户的。在电力网络中，发电厂、变电站、变压器是节点，而输电线路是边。电力工程师们需要仔细规划这些边的连接方式，确保电能够高效、安全地送达每一户人家。

航空网络：当你坐飞机去北京或者上海的时候，你其实也在一个「航空网络」中旅行。每一个机场是一个节点，每一条航线是连接两个机场的边。航空公司需要用图论来规划航线，确保飞机能够高效地将旅客送达目的地。

商业网络：在经济学中，「图」也发挥着重要作用。想象一下一家手机制造商的供应链：供应商提供零部件，工厂进行组装，批发商负责分销，零售商负责销售。这些环节通过物流、资金流相互连接，形成了一个复杂的商业网络。

1.3 图的解剖课：深入了解节点与边

通过前面的例子，你应该已经对「图」这个概念有了比较直观的认识。现在，让我们更深入地了解一下图的两个核心组成部分——节点和边。

1.3.1 节点的秘密

在数学中，我们通常用大写字母 V（Vertex的首字母）来表示节点的集合。如果有一个图包含5个节点，我们可以把它们记作：

$$V = \{v_1, v_2, v_3, v_4, v_5\}$$

这里的 $v_1, v_2, v_3, v_4, v_5$ 就是这5个节点的名称。就像每个人都有名字一样，每个节点也需要一个标识符来区分彼此。

节点可不只是一个简单的点！在实际应用中，每个节点可以携带丰富的信息。这些信息叫做节点的「属性」（Attribute）。

例如，在一个社交网络图中：

• 节点「你」可能有属性：姓名 = "小明"，年龄 = 10岁，爱好 = ["足球", "阅读"]
• 节点「小红」可能有属性：姓名 = "小红"，年龄 = 10岁，爱好 = ["舞蹈", "绘画"]

在一个城市交通图中：

• 节点「火车站」可能有属性：名称 = "北京站"，年客流量 = 1.2亿人次
• 节点「机场」可能有属性：名称 = "首都机场"，跑道数量 = 3条

节点还可以按照它们的特点分成不同的类型。就像一个公司里有不同职位的员工，图的节点也有「角色」之分。在某些图中，所有节点都是平等的；但在另一些图里，节点有主次之分。

在家族谱系图中，有些节点特别重要——它们没有指向自己的边（也就是说，不是自己的父母），我们把这些节点叫做「根节点」，就像爷爷和奶奶。相反，有些节点没有子节点（也就是说，没有孩子），我们把它们叫做「叶子节点」，就像还没有结婚的叔叔阿姨。

1.3.2 边的艺术

说完节点，让我们来看看边。边用大写字母 E（Edge的首字母）表示。边是连接两个节点的桥梁，它描述了节点之间的关系。

无向边 vs 有向边

根据边是否有方向，图可以分为「无向图」和「有向图」。

在无向图中，边没有方向，就像一条没有箭头的水管。如果小明和小红是好朋友，那么从小明的角度看，他们是好朋友；从小红角度看，他们也是好朋友。这种关系是对称的。所以，无向边通常用来描述「双向」的关系，比如朋友关系、邻居关系、道路连接等。

在有向图中，边有明确的方向，用箭头表示。如果你在微博上关注了一个人，但那个人没有关注你，那么这个关系就是单向的——你指向他，但他不指向你。有向边通常用来描述「单向」关系，比如网页之间的链接、社交网络中的关注关系、家族中的血缘传承等。

用数学语言来描述的话：

• 无向图中的边可以表示为无序对 $\{v_i, v_j\}$
• 有向图中的边可以表示为有序对 $(v_i, v_j)$，表示从 $v_i$ 指向 $v_j$

有权边 vs 无权边

根据边是否带有数值信息，边还可以分为「有权边」和「无权边」。

无权边只表示两个节点之间是否存在连接，是就是是，不是就是不是。就像电路的开关，只有「通」和「断」两种状态。

有权边则携带了额外的信息。比如在交通图中，有权边可以表示两个路口之间的距离；在社交网络中，有权边可以表示两个人之间的亲密程度；在金融网络中，有权边可以表示两个公司之间的交易金额。

用数学语言来描述的话，每一条有权边 $e$ 都关联着一个权重 $w(e)$。这个权重可以是距离、时间、花费，甚至是概率或者其他任何有意义的数值。

1.3.3 认识完全图与稀疏图

现在你已经了解了节点和边的基本概念，让我们来看看图的两个有趣的「性格特点」。

假设你班上有30个同学，每一个同学都和其他所有同学是好朋友。在图中，这意味着每两个节点之间都有一条边相连。这种情况叫做「完全图」。

完全图的边数有一个特殊的计算公式。如果一个完全图有 $n$ 个节点，那么它包含的边数为：

$$E = \frac{n \times (n-1)}{2}$$

当 $n = 30$ 时，$E = \frac{30 \times 29}{2} = 435$ 条边。这意味着，如果有435对同学成为了朋友，那么你们班就形成了一个完全的朋友关系图！

但是在真实世界中，大多数图都不是完全图。相比于完全图，真实世界的图往往更加「稀疏」——每个节点只和少数几个其他节点相连。

比如在社交网络中，虽然你可能有很多朋友，但不可能和全世界所有人都成为朋友。据统计，普通人平均有150个左右的好友关系（这在社会学研究中叫做「邓巴数字」）。假设微信有10亿用户，如果是一个完全图，那将会有天文数字般的边数，但实际上真实的朋友关系网络要稀疏得多。

```mermaid graph TB subgraph "完全图（小型示例）" FA["节点 A"] --- FB["节点 B"] FA --- FC["节点 C"] FA --- FD["节点 D"] FB --- FC FB --- FD FC --- FD end

subgraph "稀疏图（小型示例）" SA["节点 A"] --- SB["节点 B"] SC["节点 C"] --- SD["节点 D"] SA --- SC end ```

在这幅对比图中，完全图的每两个节点之间都有边相连；而稀疏图的节点之间只有少数几条边。你能数一数右边稀疏图有多少条边吗？

1.4 图的表示方法：让计算机读懂世界

我们人类可以用眼睛看到图，用笔画出图。但是计算机是怎么「看到」和「存储」图的呢？这是个好问题！让我们一起来了解一下计算机科学家们发明的几种表示图的方法。

1.4.1 邻接矩阵：方格中的秘密

想象一个巨大的棋盘，每一个小格子要么是黑色，要么是白色。在计算机中，我们可以用一个「矩阵」来存储图的信息。这个矩阵叫做「邻接矩阵」（Adjacency Matrix）。

对于一个有 $n$ 个节点的图，邻接矩阵是一个 $n \times n$ 的方阵。矩阵中的第 $i$ 行第 $j$ 列的元素，表示节点 $v_i$ 和节点 $v_j$ 之间的关系。

如果两个节点之间有边相连，我们就在对应的格子里写上 1（或者边的权重）；如果没有边，就写上 0。

```mermaid graph TD A["🅰️ 节点 A"] --- B["🅱️ 节点 B"] A --- C["🅲 节点 C"] B --- C B --- D["🅳 节点 D"] C --- D ```

上面这个图用邻接矩阵表示就是：

$$ \begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{bmatrix} $$

让我们来解读一下这个矩阵：

• 第1行第2列是 1，表示节点A和节点B之间有边相连 ✓
• 第1行第3列是 1，表示节点A和节点C之间有边相连 ✓
• 第1行第4列是 0，表示节点A和节点D之间没有边 ✗

邻接矩阵的优点是查询两个节点之间是否有边非常快——只需要查看对应位置的值就可以了，时间复杂度是 $O(1)$。但缺点是，当节点数量很大但边很少的时候，会浪费很多存储空间——因为矩阵中大部分位置都是0。

1.4.2 邻接表：链表的朋友圈

除了矩阵之外，还有一种更节省空间的表示方法，叫做「邻接表」（Adjacency List）。

邻接表的核心思想是：对于每一个节点，记录它的「邻居」有哪些。就像你在通讯录里给每个朋友建立一个列表，记录他们各自的联系方式一样。

对于上面那个图，用邻接表表示就是：

• 节点 A 的邻居：B, C
• 节点 B 的邻居：A, C, D
• 节点 C 的邻居：A, B, D
• 节点 D 的邻居：B, C

邻接表的优点是节省空间，特别是对于稀疏图来说效果明显。而且，遍历一个节点的所有邻居也非常方便。缺点是判断两个指定节点之间是否有边需要遍历邻居列表，效率不如邻接矩阵。

1.4.3 边的列表：简洁的记录方式

还有一种更直接的方法，叫做「边的列表」（Edge List）。

顾名思义，边的列表就是把所有边都列出来。每一条边用两个节点来表示。如果是加权图，还可以加上权重。

对于上面那个图，用边的列表表示就是： ``` (A, B) (A, C) (B, C) (B, D) (C, D) ```

边的列表非常简洁，特别适合边的数量不多的情况。但如果你想查询一个节点的邻居有哪些，就需要遍历整个列表，效率不高。

这三种表示方法各有优缺点，在实际应用中，计算机科学家会根据具体的问题选择最合适的方法。就像不同的工具适合不同的工作一样——钳子适合拧螺丝，锤子适合钉钉子，选择正确的工具才能让工作更有效率。

1.5 图的度数：衡量节点的社交能力

了解了图的表示方法之后，让我们再来学习一个有趣的概念——「度数」。

1.5.1 什么是度数？

在一个图中，一个节点有多少条边和它相连，就叫做这个节点的「度」（Degree）。

• 在无向图中，节点的度就是与它相连的边的数量
• 在有向图中，节点的度分为「入度」（In-degree）和「出度」（Out-degree）
• 入度：有多少条边指向这个节点
• 出度：这个节点指向多少其他节点

```mermaid graph LR A["🅰️ 节点 A"] -->|"出度+1"| B["🅱️ 节点 B"] C["🅲 节点 C"] -->|"入度+1"| A A --> D["🅳 节点 D"] E["🅴 节点 E"] --> A ```

在上面的有向图中：

• 节点A的入度是2（来自节点C和节点E）
• 节点A的出度是2（指向节点B和节点D）
• 所以节点A的总度是4

1.5.2 度的分布：社交网络的秘密

有趣的是，在真实世界的网络中，节点的度分布往往遵循一种特殊的规律——「幂律分布」（Power Law Distribution）。

这意味着什么呢？简单来说就是：大多数节点的度很低，只有少数节点有非常高的度。

以社交网络为例：

• 大多数人可能只有几十个好友
• 但像明星、网红这样的「超级节点」，可能有几百万甚至几千万的粉丝

这种「富者愈富」的现象在网络中非常普遍，叫做「马太效应」（Matthew Effect）。就像网页之间的链接一样——著名的网站（比如搜索引擎、社交媒体）被无数其他网页链接，而大多数默默无闻的小网站只有很少的