17 图论

17 图论

什么是图结构：

在计算机程序中，图结构也是一种非常常见的数据结构。
- 但是，图论其实是一个非常大的话题。
- 我们通过本章的学习来认识一下关于图的一些内容 - 图的抽象数据类型 - 一些算法实现。
什么是图？
- 图结构是一种与树结构有些相似的数据结构。
- 图论是数学的一个分支，并且在数学的概念上，树是图的一种。
- 它以图为研究对象，研究顶点和边组成图形的数学理论和方法。
- 主要研究的目的是事物之间的关系，顶点代表事物，边代表两个事物之间的关系。
我们知道树可以用来模拟很多现实的数据结构。
- 比如：家谱/公司组织架构等等。
- 那么图长什么样子呢？或者什么样的数据使用图来模拟更合适呢？

图结构的应用案例：

人与人之间的关系网，你可能跟某个人没有直接关系但是同一个顶点，可能会使得你们有非直接关系。
- 科学家们在观察人与人之间的关系网时，还发现了六度空间理论。
六度空间理论
- 理论上认为世界上任何两个互相不认识的两个人。
- 只需要很少的中间人就可以建立起来联系。
- 并非一定经过六步，只要需要很少的步骤。

图结构的特点
17 图论 - 图2

那么什么是图？
- 我们会发现，上面的结点（其实图中交顶点Vertex）之间的关系，是不能使用树来表示的。
- 使用几叉树都不可以模拟。
- 这个时候，我们就可以使用图来模拟它们。
图通常有什么特点？
- 一组顶点：通常用V（Vertex）表示顶点的集合。
- 一组边：通常用E（Edge）表示边的集合。
  - 边是顶点和顶点之间的连线。
  - 边可以是有向的，也可以是无向的。
  - 比如A —- B ,通常表示无向，A — > B ，通常表示有向。

七桥问题

18世纪著名数学问题之一。
- 在戈尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来：

17 图论 - 图3

有人提出一个问题：一个人怎样才能不重复，不遗漏地一次走完七座桥，最后回到出发点。
- 1735年，有几名大学生写信给当时正在俄罗斯的皮德斯堡科学院任职的瑞典天才数学加欧拉，请他帮忙解决这个问题。
欧拉亲自观察了哥伦斯堡的七桥后，认真思考走法，但是始终没有成功，于是他怀疑七桥问题是不是无解的。
1736年29岁的欧拉向圣彼得堡科学院递交了《戈尼斯堡的七座桥》的论文，在解答问题的同时，开创了数学的一个新的分支 —- 图论与几何拓扑，也由此展开了数学史上的新历程。

欧拉解答

他不仅解决了此问题，且给出了连通图可以一笔画出来的必要条件的：

17 图论 - 图4 此图是七座桥的抽象。

奇点的数目不是0个就是2个。
连到一点的边的数目如是奇数条，就称为奇点。
如果是偶数条就称之为偶点。
想要一笔画成，必须中间点均是偶点。
也就是说有来路必有另一条去路，奇点只可能在两端，因此任何图都能一笔画成，奇点要么没有要么在两端。
- 个人思考：
欧拉在思考这个问题的时候，不再是实际的问题去考虑，而是将岛和桥抽象成了点和线。
抽象是数学的本质，而编程我们也一再强调抽象的重要性。
汇编语言是对机器语言的抽象，高级语言是对汇编语言的抽象。
操作系统是对硬件的抽象，应用程序在操作系统的基础上构建。

抽象示意图

图的术语

顶点：
- 顶点刚才我们已经介绍过了，表示图中的一个节点。
- 比如的话：地铁中某个站/村庄中的某房舍/互联网中的某台主机/人机关系中的人。
边：
- 边表示顶点和顶点之间的连线。
- 比如地铁中两个站点之间的直接连线，就是一个边。
- 注意：这里的边不要叫做路径，路径有其它的概念，待会我们会介绍到。
- 之前的图中：0-1有一条边， 1-2有一条边， 0-2没有边。
相邻顶点：
- 由一条边连接在一起的顶点称为相邻顶点。
- 比如 0 - 1 是相邻的，0 - 3 是相邻的，0 - 2 不是相邻的。
度：
- 一个顶点的度是相邻顶点的数量。
- 比如0顶点和其它两个顶点相连，0顶点的度是2。
- 比如1顶点和其它四个顶点相连，1顶点的度就是4。
路径：
- 路径是指顶点v1，v2…，vn的一个连续序列，如图 0 1 5 9 就是就是一个路径。
- 简单路径：简单路径要求不包含重复顶点，比如 0 1 5 9是一条简单路径。
- 回路：第一个顶点和最后一个顶点相同的路径称为回路，比如 0 1 5 6 3 0 。
无向图：
- 上面的图就是一张无向图，0 可以走到 1，1 也可以走到 0，方向不是固定的。
有向图：
- 有向图表示图中的边是有固定方向的。
- 比如 0 -》1，不能保证一定可以 1 -》0，要根据方向来定。
无权图：
- 这个图就是一张无权图（边也可以认为是线，没有携带权重）。
- 这个图的边是没有任何意义的。
- 不能说 0 - 1 的边，比4 - 9 的边更远或者用的时间更长。
带权图：
- 带权图表示边有一定的权重，。
- 这里的权重可以是任意你希望表示的数据；
- 比如距离或者花费的时间或者票价。

图的表示

怎么在程序中表示图？
- 我们知道一个图包含很多顶点，另外包含顶点和顶点之间的连线（边）。
- 这两个都是非常重要的图信息，因此都需要在程序中体现出来。
顶点和表示相对简单，我们先讨论顶点的表示：
- 上面的顶点，我们抽象成了 1 2 3 4，也可以抽象成 A B C D。
- 后面的案例总，我们使用 A B C D。
- 那么这些 A B C D 我们可以使用一个数组来存储起来（储存所有的顶点）。
- 当然 A B C D有可能还表示其它含义的数据（比如村庄的名字）。
那么边怎么表示呢？
- 因为边是两个顶点之间的关系，所以表示起来会稍麻烦一些。
- 下面，我们具体讨论一下边常见的表示方式。

邻接矩阵

一种比较常见的表示图的方式：邻接矩阵。
- 邻接矩阵让每个节点和一个整数相关联，该整数最为数组的下标值。
- 我们用一个二维数组来表示顶点之间的连接。
画图表示：
图片解析：
- 在二维数组中，0表示没有连线，1表示有连线。
- 通过二维数组，我们可以很快的找到一个顶点和哪些顶点有连线（比如A顶点，只需要遍历第一杠即可）。
- 另外， A - A , B - B（也就是顶点自己的连线），通常使用0表示（自回路）。
邻接矩阵的问题：
- 邻接矩阵还有一个比较严重的问题，就是如果图是一个稀疏图。
- 那么矩阵中将存在大量的0，这意味着我们浪费了计算机存储空间来表示了根本不存在的边。

邻接表

另外一个常用的表示图的方式：邻接表
- 邻接表由图中每个顶点以及和顶点相邻的顶点列表的组成。
- 这个列表有很多种方式来存储：数组/链表/字典（哈希表）都可以。
图片展示：
图片解析：
- 其实图片比较容易理解。
- 比如我们要表示A顶点有关联的顶点（边），A和B/C/D 有边。
- 那么我么可以通过A找到对应的数组/链表/字典，再取出其中的内容就可以了。
邻接表的问题：
- 邻接表计算“出度”是比较简单的（出度：指向别人的数量，入度：指向自己的数量）
- 邻接表如果需要计算有向图的“入度”，那么是一件非常麻烦的事情。
- 它必须构造一个“逆邻接表”，才能有效的计算“入度”，但是开发中“入度”相对用的比较少。

创建图类

创建Graph类

function Graph() {
// 属性
this.vertexes = [];// 存储顶点
this.adjList = new Dictionay(); // 存储边

// 方法
}**

代码解析：
- 创建Graph的构造函数，这个我们在封装其它数据结构的时候已经非常熟悉了。
- 定义两个属性：
  - vertests：用于存储所有的顶点，我们说过使用一个数组来保持。
  - adjList：adj是adjoin的缩写，邻接的意思，adjList用于存储所有的边，我们这里采用邻接表的形式。
- 之后，我们再来定义一些方法以及实现一些算法就是一个完整的图类了。

创建图的顶点和边：
Dictionay 代码实现：
function Dictionay() {
// 字典属性
this.items = {};
// 这只字典key:value
Dictionay.prototype.set = function (key, value) {
this.items[key] = value;
}
// 判断是否存在
Dictionay.prototype.has = function (key) {
return this.items.hasOwnProperty(key);
}
// 删除某一项
Dictionay.prototype.remove = function (key) {
if (!this.has(key)) return false;
delete this.items[key];
return true;
}
// 获取值
Dictionay.prototype.get = function (key) {
return this.has(key) ? this.items[key] : undefined;
}
// 使用Object的keys方法返回一个对象的key,数组形式。
Dictionay.prototype.keys = function () {
return Object.keys(this.items);
}
// 使用Object的values方法返回一个对象的values,数组形式。
Dictionay.prototype.values = function () {
return Object.values(this.items);
}
// 获取大小这里可以直接返回长度，也就是第一层对象的个数。
Dictionay.prototype.size = function () {
return this.keys.length;
}
// 清空这个对象
Dictionay.prototype.clear = function () {
this.items = {};
}
}
graph 代码实现：
// 封装图结构 graph
function Graph() {
// 属性：顶点（数组）/边（字典）
this.vertexes = [];// 存储顶点
this.adjoinList = new Dictionay(); // 存储边

// 方法
// 添加顶点的方式
Graph.prototype.addVertex = function (v) {
this.vertexes.push(v);
this.adjoinList.set(v, []);
}
// 添加边的方式
Graph.prototype.addAdjoin = function (v1, v2) {
this.adjoinList.get(v1).push(v2);
this.adjoinList.get(v2).push(v1);
}
// toString方法
Graph.prototype.toString = function () {
let resultString = ‘’;
for (let i = 0; i < this.vertexes.length; i++) {
resultString += this.vertexes[i] + “->”;
let adjoinList = this.adjoinList.get(this.vertexes[i]);
for (let j = 0; j < adjoinList.length; j++) {
resultString += adjoinList[j];
}
resultString += “\n”;
}
return resultString;
}
}**

图的遍历

图的遍历思想
- 图的遍历思想和树的遍历思想是一样的。
- 图的遍历意味着需要将图中每个顶点访问一遍，并且不能有重复的访问。
有两种算法可以对图进行遍历
- 广度优先搜索（Breadth-First Search，简称BFS）
- 深度优先搜索（Depth-First Search，简称DFS）
- 两种遍历算法，都需要明确指定第一个被访问的顶点。
它们的遍历过程分布是怎么样呢？
- 我们以一个迷宫关灯为例。
- 现在需要你进入迷宫，将迷宫中的灯一个个关掉，你会怎么关呢？

遍历的思想

两种算法的思想：
- BFS：基于队列，入队列的顶点先被探索。
- DFS：基于栈或使用递归，通过将顶点存入栈中，顶点是沿着路径被探索的，存在新的相邻顶点就去访问。
为了记录顶点是否被访问过，我们使用三种颜色来反应它们的状态
- 白色：表示该顶点还没有被访问。
- 灰色：表示该顶点被访问过，但并未被探索过。
- 黑色：表示该顶点被访问过且被完全探索过。

广度优先搜索

广度优先搜索算法的思路：
- 广度优先算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问一层。
- 先宽后深的访问顶点。
图解BFS
广度优先搜索的实现：
创建一个队列Q
将v标注为被发现的（灰色），并将v入队列Q
如果Q非空，执行下面的步骤：
- 将v从Q中取出队列。
- 将v标注为被发现的灰色。
- 将v所有的未被访问过的邻接点（白色），加入到队列中。
- 将v标志位黑色。
  
  图解中先访问到了A被标记为灰色，然后探测（此时A应该被标记为黑色了，代码里我们把这个标记放在一个colors对象里作为一个对照表），探测结果是发现了B C D 而后存起来到未被访问的队列，接着逐个访问，B 探测后发现了E F然后也存起来（B应该标记为黑色了并且应该被排除白色队列中），此时存起来发现还属于白色队列的数据有 C D E F，接着继续逐个探测遍历数据，有发现就加入未被访问的队列，被探索后标记黑色离开这里属于白色的队列，直到这个白色队列被全部探索完为止。

实现代码：
// 实现广度优先搜索（Breadth-First Search）
Graph.prototype.bfs = function (initV, handler) {

// 1.初始化颜色
let colors = this.initializeColor();

// 2.创建队列
let queue = new Queue();

// 3.将顶点加入到队列中
queue.enqueue(initV);

// 4.循环从队列中取出元素
while (!queue.isEmpty()) {
// 4.1 从队列中取出一个顶点
let v = queue.dequeue();

// 4.2 获取和顶点相连的另外顶点
let vList = this.adjoinList.get(v);

// 4.3 将v的颜色设置成灰色
colors[v] = “gray”;

// 4.4 遍历所有的顶点，并且加入队列中
for (let i = 0; i < vList.length; i++) {
let e = vList[i];
if (colors[e] == “white”) {
colors[e] = ‘gray’;
queue.enqueue(e);
}
}

// 4.5 访问顶点
handler(v);

// 4.6将顶点设置成黑色
colors[v] = “black”;
}
}**

深度优先搜索

深度搜索的思路：
- 深度优先搜索算法将会从第一个指定的顶点开始遍历图，沿着路径路径知道这条路径最后被访问了。
- 接着原来回退并探索下一条路径。
```
 ![](https://cdn.nlark.com/yuque/0/2021/png/12698677/1614765573123-5894bac1-8613-4368-9cd4-19b7ebdda77b.png#width=240)
```
深度优先搜索算法的实现：
- 广度优先搜索算法我们使用的是队列，这里可以使用栈完成，也可以使用递归。
- 方便代码书写，我们还是使用递归（递归本质上就是函数栈的调用）。

实现代码：
// 深度优先搜索（Depth-First Search）
Graph.prototype.dfs = function (intiV, handler) {
// 1. 初始化颜色
let colors = this.initializeColor();

  // 2.从某个顶点开始依次递归访问<br />      this.dfsVisit(intiV, colors, handler);<br />    }
Graph.prototype.dfsVisit = function (v, colors, handler) {<br />      // 1.将颜色设置未灰色<br />      colors[v] = "gray";
  // 2.处理v顶点<br />      handler(v);
  // 3.访问v相连的顶点<br />      let vList = this.adjoinList.get(v);<br />      for (let i = 0; i < vList.length; i++) {<br />        let e = vList[i];<br />        if (colors[e] == "white") {<br />          this.dfsVisit(e, colors, handler);<br />        }<br />      }<br />      // 4.将v设置成黑色<br />      colors[v] = "black";<br />    }