一, 图论
1.1. 图的简介
什么是图?
图结构是一种与树结构有些相似的数据结构;
图论是数学的一个分支, 并且, 在数学中, 树是图的一种;
图论以图为研究对象, 研究顶点和边组成的图形的数学理论和方法;
主要的研究目的为: 事物之间的联系, 顶点代表事物, 边代表两个事物间的关系;
图的特点:
一组顶点: 通常用 V (Vertex)表示顶点的集合;
一组边: 通常用 E (Edge)表示边的集合;
边是顶点和顶点之间的连线;
边可以是有向的, 也可以是无向的. 比如 A----B 表示无向, A ---> B 表示有向;
图的常用术语:
顶点: 表示图中的一个节点;
边: 表示顶点和顶点给之间的连线;
相邻顶点: 由一条边连接在一起的顶点称为相邻顶点;
度: 一个顶点的度是相邻顶点的数量;
路径:
简单路径: 简单路径要求不包含重复的顶点;
回路: 第一个顶点和最后一个顶点相同的路径称为回路;
无向图: 图中的所有边都是没有方向的;
有向图: 图中的所有边都是有方向的;
无权图: 无权图中的边没有任何权重意义;
带权图: 带权图中的边有一定的权重含义;
1.2. 图的表示
邻接矩阵
表示图的常用方式为: 邻接矩阵.
可以使用二维数组来表示邻接矩阵;
邻接矩阵让每个节点和一个整数相关联, 该整数作为数组的下标值;
使用一个二维数组来表示顶点之间的连接;
如上图所示:
二维数组中的 0 表示没有连线, 1 表示有连线;
如: A[ 0 ] [ 3 ] = 1, 表示 A 和 C 之间有连接;
邻接矩阵的对角线上的值都为 0, 表示 A - A ,B - B, 等自回路都没有连接(自己与自己之间没有连接);
若为无向图, 则邻接矩阵应为对角线上元素全为 0 的对称矩阵;
邻接矩阵的问题:
如果图是一个稀疏图, 那么邻接矩阵中将存在大量的 0, 造成存储空间的浪费;
邻接表
另外一种表示图的常用方式为: 邻接表.
邻接表由图中每个顶点以及和顶点相邻的顶点列表组成;
这个列表可用多种方式存储, 比如: 数组 / 链表 / 字典 (哈希表) 等都可以;
如上图所示:
图中可清楚看到 A 与 B,C,D 相邻, 假如要表示这些与 A 顶点相邻的顶点 (边), 可以通过将它们作为 A 的值(value) 存入到对应的数组 / 链表 / 字典中.
之后, 通过键(key)A 可以十分方便地取出对应的数据;
邻接表的问题:
邻接表可以简单地得出出度, 即某一顶点指向其他顶点的个数;
但是, 邻接表计算入度 (指向某一顶点的其他顶点的个数称为该顶点的入度) 十分困难. 此时需要构造逆邻接表才能有效计算入度;
二, 封装图结构
在实现过程中采用邻接表的方式来表示边, 使用字典类来存储邻接表.
2.1. 添加字典类和队列类
首先需要引入之前实现的, 之后会用到的字典类和队列类:
- // 封装字典类
- function Dictionary(){
- // 字典属性
- this.items = {}
- // 字典操作方法
- // 一. 在字典中添加键值对
- Dictionary.prototype.set = function(key, value){
- this.items[key] = value
- }
- // 二. 判断字典中是否有某个 key
- Dictionary.prototype.has = function(key){
- return this.items.hasOwnProperty(key)
- }
- // 三. 从字典中移除元素
- Dictionary.prototype.remove = function(key){
- //1. 判断字典中是否有这个 key
- if(!this.has(key)) return false
- //2. 从字典中删除 key
- delete this.items[key]
- return true
- }
- // 四. 根据 key 获取 value
- Dictionary.prototype.get = function(key){
- return this.has(key) ? this.items[key] : undefined
- }
- // 五. 获取所有 keys
- Dictionary.prototype.keys = function(){
- return Object.keys(this.items)
- }
- // 六. size 方法
- Dictionary.prototype.keys = function(){
- return this.keys().length
- }
- // 七. clear 方法
- Dictionary.prototype.clear = function(){
- this.items = {}
- }
- }
- // 基于数组封装队列类
- function Queue() {
- // 属性
- this.items = []
- // 方法
- // 1. 将元素加入到队列中
- Queue.prototype.enqueue = element => {
- this.items.push(element)
- }
- // 2. 从队列中删除前端元素
- Queue.prototype.dequeue = () => {
- return this.items.shift()
- }
- // 3. 查看前端的元素
- Queue.prototype.front = () => {
- return this.items[0]
- }
- // 4. 查看队列是否为空
- Queue.prototype.isEmpty = () => {
- return this.items.length == 0;
- }
- // 5. 查看队列中元素的个数
- Queue.prototype.size = () => {
- return this.items.length
- }
- // 6.toString 方法
- Queue.prototype.toString = () => {
- let resultString = ''
- for (let i of this.items){
- resultString += i + ' '
- }
- return resultString
- }
- }
2.2. 创建图类
先创建图类 Graph, 并添加基本属性, 再实现图类的常用方法:
- // 封装图类
- function Graph (){
- // 属性: 顶点(数组)/ 边(字典)
- this.vertexes = [] // 顶点
- this.edges = new Dictionary() // 边
- }
2.3. 添加顶点与边
如图所示:
创建一个数组对象 vertexes 存储图的顶点; 创建一个字典对象 edges 存储图的边, 其中 key 为顶点, value 为存储 key 顶点相邻顶点的数组.
代码实现:
- // 添加方法
- // 一. 添加顶点
- Graph.prototype.addVertex = function(v){
- this.vertexes.push(v)
- this.edges.set(v, []) // 将边添加到字典中, 新增的顶点作为键, 对应的值为一个存储边的空数组
- }
- // 二. 添加边
- Graph.prototype.addEdge = function(v1, v2){// 传入两个顶点为它们添加边
- this.edges.get(v1).push(v2)// 取出字典对象 edges 中存储边的数组, 并添加关联顶点
- this.edges.get(v2).push(v1)// 表示的是无向表, 故要添加互相指向的两条边
- }
2.4. 转换为字符串输出
为图类 Graph 添加 toString 方法, 实现以邻接表的形式输出图中各顶点.
代码实现:
- // 三. 实现 toString 方法: 转换为邻接表形式
- Graph.prototype.toString = function (){
- //1. 定义字符串, 保存最终结果
- let resultString = ""
- //2. 遍历所有的顶点以及顶点对应的边
- for (let i = 0; i <this.vertexes.length; i++) {// 遍历所有顶点
- resultString += this.vertexes[i] + '-->'
- let vEdges = this.edges.get(this.vertexes[i])
- for (let j = 0; j <vEdges.length; j++) {// 遍历字典中每个顶点对应的数组
- resultString += vEdges[j] + ' ';
- }
- resultString += '\n'
- }
- return resultString
- }
测试代码:
- // 测试代码
- //1. 创建图结构
- let graph = new Graph()
- //2. 添加顶点
- let myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
- for (let i = 0; i < myVertexes.length; i++) {
- graph.addVertex(myVertexes[i])
- }
- //3. 添加边
- graph.addEdge('A', 'B')
- graph.addEdge('A', 'C')
- graph.addEdge('A', 'D')
- graph.addEdge('C', 'D')
- graph.addEdge('C', 'G')
- graph.addEdge('D', 'G')
- graph.addEdge('D', 'H')
- graph.addEdge('B', 'E')
- graph.addEdge('B', 'F')
- graph.addEdge('E', 'I')
- //4. 输出结果
- console.log(graph.toString());
测试结果:
2.5. 图的遍历
图的遍历思想:
图的遍历思想与树的遍历思想一样, 意味着需要将图中所有的顶点都访问一遍, 并且不能有重复的访问(上面的 toString 方法会重复访问);
遍历图的两种算法:
广度优先搜索(Breadth - First Search, 简称 BFS);
深度优先搜索(Depth - First Search, 简称 DFS);
两种遍历算法都需要指定第一个被访问的顶点;
为了记录顶点是否被访问过, 使用三种颜色来表示它们的状态
白色: 表示该顶点还没有被访问过;
灰色: 表示该顶点被访问过, 但其相邻顶点并未完全被访问过;
黑色: 表示该顶点被访问过, 且其所有相邻顶点都被访问过;
首先封装 initializeColor 方法将图中的所有顶点初始化为白色, 代码实现如下:
- // 四. 初始化状态颜色
- Graph.prototype.initializeColor = function(){
- let colors = []
- for (let i = 0; i < this.vertexes.length; i++) {
- colors[this.vertexes[i]] = 'white';
- }
- return colors
- }
广度优先搜索
广度优先搜索算法的思路:
广度优先搜索算法会从指定的第一个顶点开始遍历图, 先访问其所有的相邻顶点, 就像一次访问图的一层;
也可以说是先宽后深地遍历图中的各个顶点;
实现思路:
基于队列可以简单地实现广度优先搜索算法:
首先创建一个队列 Q(尾部进, 首部出);
调用封装的 initializeColor 方法将所有顶点初始化为白色;
指定第一个顶点 A, 将 A 标注为灰色(被访问过的节点), 并将 A 放入队列 Q 中;
循环遍历队列中的元素, 只要队列 Q 非空, 就执行以下操作:
先将灰色的 A 从 Q 的首部取出;
取出 A 后, 将 A 的所有未被访问过 (白色) 的相邻顶点依次从队列 Q 的尾部加入队列, 并变为灰色. 以此保证, 灰色的相邻顶点不重复加入队列;
A 的全部相邻节点加入 Q 后, A 变为黑色, 在下一次循环中被移除 Q 外;
代码实现:
- // 五. 实现广度搜索(BFS)
- // 传入指定的第一个顶点和处理结果的函数
- Graph.prototype.bfs = function(initV, handler){
- //1. 初始化颜色
- let colors = this.initializeColor()
- //2. 创建队列
- let que = new Queue()
- //3. 将顶点加入到队列中
- que.enqueue(initV)
- //4. 循环从队列中取出元素, 队列为空才停止
- while(!que.isEmpty()){
- //4.1. 从队列首部取出一个顶点
- let v = que.dequeue()
- //4.2. 从字典对象 edges 中获取和该顶点相邻的其他顶点组成的数组
- let vNeighbours = this.edges.get(v)
- //4.3. 将 v 的颜色变为灰色
- colors[v] = 'gray'
- //4.4. 遍历 v 所有相邻的顶点 vNeighbours, 并且加入队列中
- for (let i = 0; i < vNeighbours.length; i++) {
- const a = vNeighbours[i];
- // 判断相邻顶点是否被探测过, 被探测过则不加入队列中; 并且加入队列后变为灰色, 表示被探测过
- if (colors[a] == 'white') {
- colors[a] = 'gray'
- que.enqueue(a)
- }
- }
- //4.5. 处理顶点 v
- handler(v)
- //4.6. 顶点 v 所有白色的相邻顶点都加入队列后, 将顶点 v 设置为黑色. 此时黑色顶点 v 位于队列最前面, 进入下一次 while 循环时会被取出
- colors[v] = 'black'
- }
- }
过程详解:
下为指定的第一个顶点为 A 时的遍历过程:
如 a 图所示, 将在字典 edges 中取出的与 A 相邻的且未被访问过的白色顶点 B,C,D 放入队列 que 中并变为灰色, 随后将 A 变为黑色并移出队列;
接着, 如图 b 所示, 将在字典 edges 中取出的与 B 相邻的且未被访问过的白色顶点 E,F 放入队列 que 中并变为灰色, 随后将 B 变为黑色并移出队列;
如 c 图所示, 将在字典 edges 中取出的与 C 相邻的且未被访问过的白色顶点 G(A,D 也相邻不过已变为灰色, 所以不加入队列)放入队列 que 中并变为灰色, 随后将 C 变为黑色并移出队列;
接着, 如图 d 所示, 将在字典 edges 中取出的与 D 相邻的且未被访问过的白色顶点 H 放入队列 que 中并变为灰色, 随后将 D 变为黑色并移出队列.
如此循环直到队列中元素为 0, 即所有顶点都变黑并移出队列后才停止, 此时图中顶点已被全部遍历.
测试代码:
- // 测试代码
- //1. 创建图结构
- let graph = new Graph()
- //2. 添加顶点
- let myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
- for (let i = 0; i < myVertexes.length; i++) {
- graph.addVertex(myVertexes[i])
- }
- //3. 添加边
- graph.addEdge('A', 'B')
- graph.addEdge('A', 'C')
- graph.addEdge('A', 'D')
- graph.addEdge('C', 'D')
- graph.addEdge('C', 'G')
- graph.addEdge('D', 'G')
- graph.addEdge('D', 'H')
- graph.addEdge('B', 'E')
- graph.addEdge('B', 'F')
- graph.addEdge('E', 'I')
- //4. 测试 bfs 遍历方法
- let result = ""
- graph.bfs(graph.vertexes[0], function(v){
- result += v + "-"
- })
- console.log(result);
测试结果:
可见, 安装了广度优先搜索的顺序不重复地遍历了所有顶点.
深度优先搜索
广度优先算法的思路:
深度优先搜索算法将会从指定的第一个顶点开始遍历图, 沿着一条路径遍历直到该路径的最后一个顶点都被访问过为止;
接着沿原来路径回退并探索下一条路径, 即先深后宽地遍历图中的各个顶点;
实现思路:
可以使用栈结构来实现深度优先搜索算法;
深度优先搜索算法的遍历顺序与二叉搜索树中的先序遍历较为相似, 同样可以使用递归来实现(递归的本质就是函数栈的调用).
基于递归实现深度优先搜索算法: 定义 dfs 方法用于调用递归方法 dfsVisit, 定义 dfsVisit 方法用于递归访问图中的各个顶点.
在 dfs 方法中:
首先, 调用 initializeColor 方法将所有顶点初始化为白色;
然后, 调用 dfsVisit 方法遍历图的顶点;
在 dfsVisit 方法中:
首先, 将传入的指定节点 v 标注为灰色;
接着, 处理顶点 V;
然后, 访问 V 的相邻顶点;
最后, 将顶点 v 标注为黑色;
代码实现:
- // 六. 实现深度搜索(DFS)
- Graph.prototype.dfs = function(initV, handler){
- //1. 初始化顶点颜色
- let colors = this.initializeColor()
- //2. 从某个顶点开始依次递归访问
- this.dfsVisit(initV, colors, handler)
- }
- // 为了方便递归调用, 封装访问顶点的函数, 传入三个参数分别表示: 指定的第一个顶点, 颜色, 处理函数
- Graph.prototype.dfsVisit = function(v, colors, handler){
- //1. 将颜色设置为灰色
- colors[v] = 'gray'
- //2. 处理 v 顶点
- handler(v)
- //3. 访问 V 的相邻顶点
- let vNeighbours = this.edges.get(v)
- for (let i = 0; i < vNeighbours.length; i++) {
- let a = vNeighbours[i];
- // 判断相邻顶点是否为白色, 若为白色, 递归调用函数继续访问
- if (colors[a] == 'white') {
- this.dfsVisit(a, colors, handler)
- }
- }
- //4. 将 v 设置为黑色
- colors[v] = 'black'
- }
过程详解:
这里主要解释一下代码中的第 3 步操作: 访问指定顶点的相邻顶点.
以指定顶点 A 为例, 先从储存顶点及其对应相邻顶点的字典对象 edges 中取出由顶点 A 的相邻顶点组成的数组:
第一步: A 顶点变为灰色, 随后进入第一个 for 循环, 遍历 A 白色的相邻顶点: B,C,D; 在该 for 循环的第 1 次循环中(执行 B),B 顶点满足: colors == "white", 触发递归, 重新调用该方法;
第二步: B 顶点变为灰色, 随后进入第二个 for 循环, 遍历 B 白色的相邻顶点: E,F; 在该 for 循环的第 1 次循环中(执行 E),E 顶点满足: colors == "white", 触发递归, 重新调用该方法;
第三步: E 顶点变为灰色, 随后进入第三个 for 循环, 遍历 E 白色的相邻顶点: I; 在该 for 循环的第 1 次循环中(执行 I),I 顶点满足: colors == "white", 触发递归, 重新调用该方法;
第四步: I 顶点变为灰色, 随后进入第四个 for 循环, 由于顶点 I 的相邻顶点 E 不满足: colors == "white", 停止递归调用. 过程如下图所示:
第五步: 递归结束后一路向上返回, 首先回到第三个 for 循环中继续执行其中的第 2,3... 次循环, 每次循环的执行过程与上面的同理, 直到递归再次结束后, 再返回到第二个 for 循环中继续执行其中的第 2,3... 次循环.... 以此类推直到将图的所有顶点访问完为止.
下图为遍历图中各顶点的完整过程:
发现表示访问了该顶点, 状态变为灰色;
探索表示既访问了该顶点, 也访问了该顶点的全部相邻顶点, 状态变为黑色;
由于在顶点变为灰色后就调用了处理函数 handler, 所以 handler 方法的输出顺序为发现顶点的顺序即: A,B,E,I,F,C,D,G,H .
测试代码:
- // 测试代码
- //1. 创建图结构
- let graph = new Graph()
- //2. 添加顶点
- let myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
- for (let i = 0; i < myVertexes.length; i++) {
- graph.addVertex(myVertexes[i])
- }
- //3. 添加边
- graph.addEdge('A', 'B')
- graph.addEdge('A', 'C')
- graph.addEdge('A', 'D')
- graph.addEdge('C', 'D')
- graph.addEdge('C', 'G')
- graph.addEdge('D', 'G')
- graph.addEdge('D', 'H')
- graph.addEdge('B', 'E')
- graph.addEdge('B', 'F')
- graph.addEdge('E', 'I')
- //4. 测试 dfs 遍历顶点
- let result = ""
- graph.dfs(graph.vertexes[0], function(v){
- result += v + "-"
- })
- console.log(result);
测试结果:
2.6. 完整实现
- // 封装图结构
- function Graph (){
- // 属性: 顶点(数组)/ 边(字典)
- this.vertexes = [] // 顶点
- this.edges = new Dictionary() // 边
- // 方法
- // 添加方法
- // 一. 添加顶点
- Graph.prototype.addVertex = function(v){
- this.vertexes.push(v)
- this.edges.set(v, []) // 将边添加到字典中, 新增的顶点作为键, 对应的值为一个存储边的空数组
- }
- // 二. 添加边
- Graph.prototype.addEdge = function(v1, v2){// 传入两个顶点为它们添加边
- this.edges.get(v1).push(v2)// 取出字典对象 edges 中存储边的数组, 并添加关联顶点
- this.edges.get(v2).push(v1)// 表示的是无向表, 故要添加互相指向的两条边
- }
- // 三. 实现 toString 方法: 转换为邻接表形式
- Graph.prototype.toString = function (){
- //1. 定义字符串, 保存最终结果
- let resultString = ""
- //2. 遍历所有的顶点以及顶点对应的边
- for (let i = 0; i < this.vertexes.length; i++) {// 遍历所有顶点
- resultString += this.vertexes[i] + '-->'
- let vEdges = this.edges.get(this.vertexes[i])
- for (let j = 0; j < vEdges.length; j++) {// 遍历字典中每个顶点对应的数组
- resultString += vEdges[j] + ' ';
- }
- resultString += '\n'
- }
- return resultString
- }
- // 四. 初始化状态颜色
- Graph.prototype.initializeColor = function(){
- let colors = []
- for (let i = 0; i < this.vertexes.length; i++) {
- colors[this.vertexes[i]] = 'white';
- }
- return colors
- }
- // 五. 实现广度搜索(BFS)
- // 传入指定的第一个顶点和处理结果的函数
- Graph.prototype.bfs = function(initV, handler){
- //1. 初始化颜色
- let colors = this.initializeColor()
- //2. 创建队列
- let que = new Queue()
- //3. 将顶点加入到队列中
- que.enqueue(initV)
- //4. 循环从队列中取出元素
- while(!que.isEmpty()){
- //4.1. 从队列中取出一个顶点
- let v = que.dequeue()
- //4.2. 获取和顶点相相邻的其他顶点
- let vNeighbours = this.edges.get(v)
- //4.3. 将 v 的颜色变为灰色
- colors[v] = 'gray'
- //4.4. 遍历 v 所有相邻的顶点 vNeighbours, 并且加入队列中
- for (let i = 0; i < vNeighbours.length; i++) {
- const a = vNeighbours[i];
- // 判断相邻顶点是否被探测过, 被探测过则不加入队列中; 并且加入队列后变为灰色, 表示被探测过
- if (colors[a] == 'white') {
- colors[a] = 'gray'
- que.enqueue(a)
- }
- }
- //4.5. 处理顶点 v
- handler(v)
- //4.6. 顶点 v 所有白色的相邻顶点都加入队列后, 将顶点 v 设置为黑色. 此时黑色顶点 v 位于队列最前面, 进入下一次 while 循环时会被取出
- colors[v] = 'black'
- }
- }
- // 六. 实现深度搜索(DFS)
- Graph.prototype.dfs = function(initV, handler){
- //1. 初始化顶点颜色
- let colors = this.initializeColor()
- //2. 从某个顶点开始依次递归访问
- this.dfsVisit(initV, colors, handler)
- }
- // 为了方便递归调用, 封装访问顶点的函数, 传入三个参数分别表示: 指定的第一个顶点, 颜色, 处理函数
- Graph.prototype.dfsVisit = function(v, colors, handler){
- //1. 将颜色设置为灰色
- colors[v] = 'gray'
- //2. 处理 v 顶点
- handler(v)
- //3. 访问 v 相连的其他顶点
- let vNeighbours = this.edges.get(v)
- for (let i = 0; i < vNeighbours.length; i++) {
- let a = vNeighbours[i];
- // 判断相邻顶点是否为白色, 若为白色, 递归调用函数继续访问
- if (colors[a] == 'white') {
- this.dfsVisit(a, colors, handler)
- }
- }
- //4. 将 v 设置为黑色
- colors[v] = 'black'
- }
- }
来源: https://www.cnblogs.com/AhuntSun-blog/p/12636692.html