走进图的神奇世界

第1章：走进图的神奇世界

你有没有想过，当我们打开手机刷朋友圈时，那些密密麻麻的好友关系是怎么被计算机记住的？当你用导航软件查找去学校的最短路线时，它是怎么快速计算出最优路径的？当你玩网络游戏时，系统是怎么在眨眼之间找到距离你最近的服务器的呢？

这些问题的答案，都藏在一个叫做“图”的神奇结构里。

别误会，这里说的“图”可不是你美术课画的风景画，也不是妈妈手机里的照片。在计算机的神奇世界里，“图”是一种用来描述事物之间关系的神奇工具。它就像一张超级关系网，能够把世界上各种各样复杂的联系都清晰地表示出来。

生活中的关系网：原来到处都是“图”

让我们先离开计算机一会儿，去看看我们熟悉的日常生活。你会发现，“图”其实一直就在我们身边，只是我们从来没有用“图”的眼光去观察它。

想象一下你们学校的班级。每个同学都是班级这个大家庭中的一员。星期一早上做广播体操时，体育老师让大家按队列站好，这时候你会发现：小明和小华是同桌，他们站在一起；小芳坐在小明的后面；小李和小王是好朋友，他们总是一起排队。

如果我们把每个同学想象成一个“小圆点”，把同学之间的好朋友关系用线连起来，那就形成了一个关系网络。瞧，这就是一个最简单的“图”——只不过它画的不是数学题，而是你和同学们的友谊。

让我们再看看家族的故事。每到春节，很多小朋友都会跟着爸爸妈妈回老家拜年。这时候，爷爷会指着墙上的族谱给你介绍：“这是你曾祖父，这是你爷爷，这是你爸爸……”家族中的每个人就像族谱上的一个名字，而“父子”“祖孙”“兄弟”这些关系，就像一条条连接线，把整个家族串联在一起。

计算机科学家们给“图”中的这些“小圆点”起了个好听的名字——节点（Node），有时也叫它们顶点（Vertex）。而连接节点的那些线，就叫做边（Edge）。有了节点和边，我们就能用一种统一的方式来描述世界上各种各样的关系了。

让我们再来看看城市里的公交线路。每个公交站台就像一个节点，两站之间开过去的公交车经过的路线就像一条边。如果你想从家去科技馆玩，你需要先查查看应该坐哪路车、在哪一站换乘——这个思考过程，其实就是在“图”上寻找路径的过程呢！

你的手指头也可以变成一张图！每个手指关节是一个节点，相邻关节之间的连接就是边。人的骨骼系统、城市的地铁网络、甚至整个互联网，都可以被看成是“图”。

走进图的世界：节点与边的奥秘

现在，我们已经知道“图”是什么了：它由两部分组成——节点和边。节点就像是图上的“居民”，而边则是连接这些居民的“道路”。

但同样是图，它们之间有什么区别呢？让我们一起来探索图的更多奥秘。

首先，我们来认识两种最重要的图：有向图和无向图。

想象你和好朋友之间的友谊关系。你是小明的好朋友，小明也是你的好朋友——这种关系是相互的。你对他说“我是你朋友”，同时他也对你说同样的话。在图中，我们用一条没有箭头的线来表示这种双向的关系，这就是无向图。

但是，在社交媒体上就有点不一样了！你可能在抖音上关注了一个你喜欢的UP主，你“关注”了他，但他不一定“关注”回你。在微博上也一样，你可以关注很多人，但很多人不一定关注你。这种关系是单向的——我认识你，但你不一定认识我。在图中，我们用带箭头的线来表示这种单向关系，有箭头的线叫做有向边，整张图就叫做有向图。

用数学的语言来说：

• **无向图**：如果两个节点之间有边，那么这条边在两个方向上都可以通行。
• **有向图**：边有方向，从一个节点指向另一个节点，就像单行道一样。

让我们来看一个具体的例子。下图展示了一个学校的选课系统：

```mermaid graph LR A["小明"] -->|选修| B["数学课"] A -->|选修| C["英语课"] D["小红"] -->|选修| B D -->|选修| D1["美术课"] E["小华"] -->|选修| C E -->|选修| B ```

在这个有向图中，箭头从学生指向课程，表示“学生选修了这门课”。小明选了数学和英语，小红选了数学和美术，小华选了英语和数学。这就是一张有向图，因为它清楚地表达了“谁选了哪门课”这种单向关系。

现在，让我们来认识另一种分类：加权图和非加权图。

假设你要从家出发去公园，有两条路可以选择：一条路很近，只要走5分钟就能到，但是要经过一座很陡的小山；另一条路远一些，需要走15分钟，但是路很平坦，是平整的塑胶步道。你会选哪一条路呢？

这时候，“距离”或“时间”就成了一个重要的参考因素。在图中，我们给边加上一个数字来表示这种“代价”，这个数字就叫做权重（Weight），而这样的图就叫做加权图。

```mermaid graph TD A["家"] -->|"5分钟/爬山"| B["公园"] A -->|"15分钟/平坦"| B A -->|"8分钟/有点陡"| C["超市"] C -->|"5分钟/平坦"| B ```

在这个例子中，每条边都标注了走过这条路径需要的时间，这就是一个加权图。而如果我们在图中只关心两个地点是否相连，不关心它们之间的距离，那就叫做非加权图。

加权图在现实中有着广泛的应用：

• **导航软件**：每条道路的权重是预计行驶时间或距离
• **航空网络**：每条航线的权重是机票价格或飞行时间
• **通信网络**：每条网络连接的权重是延迟或带宽

图的大家族：更多种类的图

除了有向/无向和加权/非加权的分类，图还有许多其他有趣的成员。让我给你介绍几个最重要的。

连通图与非连通图

想象一个由几个小岛组成的群岛。每个小岛内部都有自己的道路系统，但是如果小岛之间没有桥梁或渡船连接，你就无法从一个岛去到另一个岛。

在图的世界里也有类似的情况。如果一张图中的任意两个节点之间都存在一条路径可以相互到达，我们就称它为连通图。反之，如果有些节点与其他节点完全隔离，没有任何边连接它们，那就叫做非连通图。

```mermaid graph TD subgraph 连通图 A1["节点A"] --> B1["节点B"] B1 --> C1["节点C"] C1 --> A1 end

subgraph 非连通图 A2["节点X"] --> B2["节点Y"] D2["节点Z"] end ```

环图：一条神奇的回路

你有没有玩过“套圈圈”的玩具？那些一圈一圈的铁丝看起来就像一个圆环。在图的世界里，如果我们从一个节点出发，沿着边走，最后又回到起点，就形成了一个环（Cycle）。

一个经典的例子就是“石头剪刀布”的循环：石头赢剪刀，剪刀赢布，布赢石头，然后石头又赢剪刀……这个循环永远不会结束。在图中，我们可以这样表示：

```mermaid graph LR A["石头"] -->|"赢"| B["剪刀"] B -->|"赢"| C["布"] C -->|"赢"| A ```

像这样所有节点都恰好有两条边连接的特殊图，被称为环图，它在计算机科学中有着重要的应用，比如计算机网络中的令牌环协议。

树：图的优雅亲戚

有一种图特别重要，它就是树（Tree）。树是一种特殊的图，它有两个特点：第一，它是没有环的；第二，它是连通的——也就是说，从任意一个节点出发，都可以到达其他任意节点。

树的样子就像一棵倒过来的树：有一个根节点在最上面，像树根一样；其他节点像树枝一样层层展开，但是不会有哪根树枝绕回来形成圈圈。

你的学校组织结构可能就像一棵树：校长在最高层，下面是各个年级的年级主任，每个年级主任下面又有各个班的班主任，每个班主任下面管理着自己的学生。一层一层，清晰明了。

```mermaid graph TD A["校长"] --> B["一年级主任"] A --> C["二年级主任"] A --> D["三年级主任"] B --> E["一班班主任"] B --> F["一班班主任"] C --> G["二班班主任"] C --> H["二班班主任"] D --> I["三班班主任"] D --> J["三班班主任"] ```

树的一个重要性质是：如果一棵树有$n$个节点，那么它一定有恰好$n-1$条边。这个规律看起来简单，但却是许多算法的基础。

完全图：人人都是朋友

想象一个 party，每个到场的人都要和所有其他人握手寒暄。如果有5个人到场，一共要握多少次手呢？

答案是10次。计算方法是：第一个人要和4个人握手，第二个人要和剩下的3个人握手（因为他已经和第一个人握过了），第三个人要和剩下的2个人握手，第四个人要和最后1个人握手，第五个人已经没有新人可以握了。所以是：4+3+2+1=10。

在图论中，如果一个图中任意两个不同的节点之间都有一条边直接相连，就把这个图叫做完全图（Complete Graph）。有5个节点的完全图记作$K_5$，就像上面我们描述的那个握手场景一样。

完全图虽然看起来很简单，但它在图论研究中却扮演着重要角色——它经常被用来测试算法的效率，因为完全图是“最复杂”的情况。

图的表示方法：计算机如何存储图

现在我们已经认识了各种各样的图，但还有一个重要的问题没有解决：计算机是怎么存储这些图的呢？

我们可以用铅笔在纸上画图，但计算机没有铅笔，它只能用数字和代码来记录信息。所以我们需要一些特殊的方法来告诉计算机：“这里有一张图，请帮我记住它。”

方法一：邻接矩阵

想象一个巨大的棋盘，每个格子里要么放着棋子，要么空着。这就是邻接矩阵（Adjacency Matrix）的基本思想。

对于一个有$n$个节点的图，我们创建一个$n \times n$的表格（矩阵）。如果节点$i$和节点$j$之间有边，我们就在第$i$行第$j$列的格子里放一个1；如果没有边，就放一个0。

让我们用小明、小华、小红、小芳四个人的友谊来举例：

```mermaid graph TD A["小明"] <--> B["小华"] A <--> C["小红"] B <--> C C <--> D["小芳"] ```

在这个友谊图中，小明和小华是好朋友，小明和小红是好朋友，小华和小红是好朋友，小红和小芳是好朋友。

如果我们要用邻接矩阵来表示这张图，首先给四个同学编号：小明是1号，小华是2号，小红是3号，小芳是4号。然后我们创建一个$4 \times 4$的表格：

| | 小明(1) | 小华(2) | 小红(3) | 小芳(4) | |-------|---------|---------|---------|---------| | 小明(1) | 0 | 1 | 1 | 0 | | 小华(2) | 1 | 0 | 1 | 0 | | 小红(3) | 1 | 1 | 0 | 1 | | 小芳(4) | 0 | 0 | 1 | 0 |

表格中的数字表示：1表示这两个人是好朋友，0表示不是好朋友。对角线上都是0，因为一个人不能是自己的朋友（在这个例子里）。

如果这是有向图，1表示“从行到列有边”。比如第二行第三列是1，表示“小华指向小红”，也就是说小华是小红的朋友。

如果这是加权图，我们可以用权重来替代0和1。比如两个城市之间的高速公路长度，或者两个城市之间的机票价格。

邻接矩阵的优点是：查询两个节点之间是否有边非常快，我们只需要看一下对应位置的数字就可以了。时间复杂度是$O(1)$，意思是说不管图有多大，查一下都是一样快的。

但是它也有缺点：如果节点很多但边很少，矩阵中会充满很多0，浪费存储空间。比如一个城市有一万个路口，但每个路口只连接3-4条路，用邻接矩阵就需要存储一个$10000 \times 10000$的巨大表格，里面大部分都是0。

方法二：邻接表

有没有更节省空间的方法呢？当然有！这就是邻接表（Adjacency List）。

邻接表的思想很简单：每个节点都有自己的“朋友圈名单”。就像你手机里的通讯录，每个联系人下面记录着他所有好朋友的联系方式。

对于刚才那个友谊图，邻接表可以这样表示：

``` 小明的好友: 小华、小红 小华的好友: 小明、小红 小红的好友: 小明、小华、小芳 小芳的好友: 小红 ```

如果用代码来表示，Python中的邻接表可能是这样的：

```python

用字典表示邻接表

graph = { "小明": ["小华", "小红"], "小华": ["小明", "小红"], "小红": ["小明", "小华", "小芳"], "小芳": ["小红"] } ```

或者用列表的列表：

```python

假设节点编号: 0=小明, 1=小华, 2=小红, 3=小芳

graph = [ [1, 2], # 小明(0)的邻居 [0, 2], # 小华(1)的邻居 [0, 1, 3], # 小红(2)的邻居 [2] # 小芳(3)的邻居 ] ```

邻接表的优点是：存储空间与边的数量成正比，而不是与节点数的平方成正比。如果一个图有1万个节点但只有3万条边，用邻接表只需要存储这3万个邻居信息，而不是1亿个表格格子。

但是邻接表也有缺点：如果我们要检查两个特定的节点之间是否有边，需要遍历其中一个节点的邻居列表，最坏情况下需要检查所有邻居，时间复杂度是$O(V)$，其中$V$是一个节点的邻居数量。

两种方法各有优劣

让我们来比较一下：

| 特性 | 邻接矩阵 | 邻接表 | |------|----------|--------| | 存储空间 | $O(V^2)$ | $O(V + E)$ | | 检查两点是否相邻 | $O(1)$ | $O(degree)$ | | 遍历所有邻居 | $O(V)$ | $O(degree)$ | | 适用场景 | 边密集的图，需要频繁查询两点关系 | 边稀疏的图，需要遍历邻居 |

这里的$V$是节点数（Vertex），$E$是边数（Edge），$degree$是一个节点的邻居数量。

在实际编程中，我们应该根据具体的问题来选择合适的表示方法。如果图的边很多（接近完全图），用邻接矩阵更合适；如果边比较少，用邻接表更节省空间。

实际代码示例

让我们用Python来实现一个简单的好友关系图：

```python class FriendGraph: """用邻接表表示的好友关系图"""

def __init__(self): self.friends = {} # 邻接表：存储每个人的好友列表

def add_person(self, name): """添加一个人""" if name not in self.friends: self.friends[name] = []

def add_friendship(self, person1, person2): """建立两人的好友关系（无向图）""" self.add_person(person1) self.add_person(person2)

if person2 not in self.friends[person1]: self.friends[person1].append(person2) if person1 not in self.friends[person2]: self.friends[person2].append(person1)

def are_friends(self, person1, person2): """检查两人是否是好友""" if person1 not in self.friends: return False return person2 in self.friends[person1]

def get_friends(self, person): """获取某人的所有好友""" if person not in self.friends: return [] return self.friends[person]

def display(self): """显示所有好友关系""" for person, friend_list in self.friends.items(): print(f"{person} 的好友: {', '.join(friend_list) if friend_list else '无'}")

创建好友关系图

classroom = FriendGraph()

添加好友关系

classroom.add_friendship("小明", "小华") classroom.add_friendship("小明", "小红") classroom.add_friendship("小华", "小红") classroom.add_friendship("小红", "小芳") classroom.add_friendship("小华", "小李")

显示结果

classroom.display()

检查好友关系

print(f"\n小明和小芳是好友吗？{classroom.are_friends('小明', '小芳')}") print(f"小明和小红是好友吗？{classroom.are_friends('小明', '小红')}") ```

运行这段代码，你会看到：

``` 小明 的好友: 小华, 小红 小华 的好友: 小明, 小红, 小李 小红 的好友: 小明, 小华, 小芳 小芳 的好友: 小红 小李 的好友: 小华

小明和小芳是好友吗？False 小明和小红是好友吗？True ```

这个简单的程序展示了如何用