本文的主题是图。与树相比，图是更通用的结构；事实上，可以把树看作一种特殊的图。
图可以用来表示现实世界中很多有意思的事物，包括道路系统、城市之间的航班、互
联网的连接，甚至是计算机专业的一系列必修课。
你在本章中会看到，一旦有了很好的表示方法，就可以用一些标准的图算法来解决那些看起来非常困难的问题。
尽管我们能够轻易看懂路线图并理解其中不同地点之间的关系，但是计算机并不具备这样的能力。不过，我们也可以将路线图看成是一张图，从而使计算机帮我们做一些非常有意思的事情。
用过互联网地图网站的人都知道，计算机可以帮助我们找到两地之间最短、最快、最便捷的路线。
计算机专业的学生可能会有这样的疑惑：自己需要学习哪些课程才能获得学位呢？图可以很
好地表示课程之间的依赖关系。下图展示了要在流沙学院获得计算机科学学位，所需学习课程
的先后顺序。
1. 术语及定义
在看了图的例子之后，现在来正式地定义图及其构成。从对树的学习中，我们已经知道了一些术语。
1.1 顶点
顶点又称节点，是图的基础部分。它可以有自己的名字，我们称作“键”。顶点也可以带有
附加信息，我们称作“有效载荷”。
1.2 边
边是图的另一个基础部分。两个顶点通过一条边相连，表示它们之间存在关系。
边既可以是单向的，也可以是双向的。如果图中的所有边都是单向的，我们称之为有向图。上面的图明显是一个有向图，因为必须修完某些课程后才能修后续的课程。
1.3 权重
边可以带权重，用来表示从一个顶点到另一个顶点的成本。例如在路线图中，从一个城市到
另一个城市，边的权重可以表示两个城市之间的距离。
2. 故事背景
2.1 人物
- 小白
- 大牛
- 新晋人物 — 出租车司机：深耕于出租车服务行业，每年数十万行程公里，资深出租车司机。
2.2 场景
我过的桥多于你走过的路
2.3 前言
图结构是一种比树结构更复杂的非线性结构。在图形结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。
某某城市的高速公路上，一辆白色 SUV 正急速向前行驶。车里的一老一少正在畅谈。镜头拉近 —— 原来是出差归来的大牛和小白两人。
“牛哥，这两天我这儿提供的伙食还行吧。”
“不错不错，你看我这都胖两斤了。招待能不好吗。”
“那是必须的，虽然说没有能回家一趟，但是这庆功酒可不能省。毕竟这可是咱们俩第一次一块儿出差。而且取得了这么好的成果。”
“说来也是，这次的工作出奇的顺利。没想到这么快就能把客户搞定。”
“怎么说我也是公司的吉祥物啊。就这么几个小客户，小 case 啦。”
“喲，什么时候成公司的吉祥物了，我怎么不知道呢？”
“这不出差回来吗，那几个客户都让咱们解决了。而且我这是第一次出差，就取得了这么好的成果，所以大家亲切的称呼我为 – 小白吉祥。”
“哈哈哈，小白吉祥，你是要笑死我，难不成你是要穿越回清朝当格格吗。”
“过分了啊牛哥，好不容易我在公司的知名度涨上去了，你可不能挖苦我。诶诶诶，司机师傅，咱们走错路了吧， 从刚才那个路口下去就到了”
“怎么可能。这条路我走了无数次，肯定是从前边下去近点儿。” 司机反驳到。
“不对不对，我每次去这儿都是从刚才那个路口下去的。肯定是那个近。” 小白心急的说道。
“那你是被坑了呗。从那里下去，最少要多5块钱的路费呢。听我的就行了。我过的桥比你走的路都多。肯定不会错的”
“好好好，那就先按照您的路线走。不过咱可说好了，如果路费真是多了，我可是不会多给的。”
“没问题，如果比你之前的路费多了，我分文不收。免费送你们过来。要是比之前少，我可是要加倍收费的”
“好，我就跟你赌这一次。不就是双倍车费吗，还是能付得起的。”
“小白啊，刚听你俩这话这会儿，我想起来一个事儿啊。咱们这几天是不是忘了点儿什么。” 大牛闪动着狡黠的目光问小白
“哦？我怎么不记得忘了什么。话说咱们这就快到地方了吧。” 小白顾左右而言他。
“别装糊涂，才这么大，记性不好可不行啊。”
“好好好，我也不装蒜了，我也知道牛哥你想问什么。放马过来吧，早死早超生，二十年后，本白还是一条好汉。”
“得了得了，说的跟要你命似的。上次咱们不是说到堆结构了吗，数据结构这块儿内容还有什么没问到的？”
“就剩下图结构了，剩下的你都问了个遍。我这左躲右躲的都没躲过你的追击。”
“既然你都知道了，那我也不废话了。来说说吧。”
“行，说就说，不过图结构可真复杂，我还真说不全。”
“说全了就不是你了。单这一种数据结构都够出好几本书的了。说基本的就行了。”
“好，那我开始了牛哥。不对的地方，您老可得提醒提醒我。”
“没问题，这都是小事儿。”
那还是先说说基本概念吧。毕竟这都是基础，如果这个都不知道，那剩下的都不用说了。
3. 图的定义
图：一种网络结构的抽象模型。是一组由边连接的顶点组成。
G = (V, E)
4. 相关概念
4.1 相邻顶点
4.2 路径
4.3 环
4.4 有向图
4.5 权
图的边存在的值成为权重：
“不错不错，概念说的都挺全的。但是只了解概念还不够。还得知道怎么表示和实现图。”
“莫着急啊牛哥，我就差一点儿就说到表示和实现了。”
“好好好，那我就安静的听着。”
听好了啊。
3. 图结构的表示方式（邻接矩阵、邻接表、关联矩阵）
3.1 邻接矩阵
纵向为顶点，横向为相邻顶点。
使用二维数组存储，如果两个顶点之间存在连接，则值为 1 ，否则为 0。
会造成一定的存储资源浪费 。
| 一种 | 乙 | C | D | 和 | F | G | H | 一世 | |
|---|---|---|---|---|---|---|---|---|---|
| 一种 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 乙 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| C | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| D | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 和 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| F | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| G | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| H | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 一世 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
3.2 邻接表
是对邻接矩阵的改进，如下所示。
我们可以使用数组、链表、字典、散列表等来表示邻接表。
| 顶点 | 相邻顶点 |
|---|---|
| 一种 | 乙—丙 |
| 乙 | A — D — E |
| C | A — F — G |
| D | 乙——我 |
| 和 | 乙 |
| F | C—H |
| G | C—H |
| H | F—G |
| 一世 | D |
3.3 关联矩阵
纵向为顶点，横向为边。适用于顶点远大于边的情况。
| e1 | e2 | e3 | e4 | e5 | e6 | e7 | e8 | e9 | |
|---|---|---|---|---|---|---|---|---|---|
| 一种 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 乙 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| C | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| D | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 和 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| F | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| G | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| H | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 一世 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
“到这里我就说完了我知道的表示图的方式，下面我来说说前端怎么创建和使用图。”
“看来你这几天的学习也没有落下，本牛很是欣慰啊。”
“这话说的，徒弟领进门，修行看个人嘛。怎么也不能拿自己的未来开玩笑不是。”
“这句话倒是说的不错，看来你已经领悟到了学习的精髓。我也不用太过担心了。”
“好了牛哥，咱们接着说？”
4. 图的创建和使用
好，下面我就说说图的创建和使用。
4.2 图的遍历
1. 遍历方法
- 深度优先搜索 —> 栈
-
2. 辅助功能
在遍历顶点的过程中，我们需要给每个节点定义两种状态，用来表示访问次数。每个顶点最多被访问两次。
白：未被访问
- 灰：被访问但是未被处理
- 黑：已被处理
3. 广度优先搜索实例解析
从第一个顶点开始遍历，访问所有相邻顶点，再访问相邻顶点的相邻顶点。直到所有顶点访问结束。
广度优先搜索图解
深度优先搜索图解
若有收获，就点个赞吧
0 人点赞
