JavaScript实现图结构

伊笑花开 發表於 2020-4-5 12:36:00

<h2 id="javascript实现图结构">JavaScript实现图结构</h2>
<h3 id="一图论">一、图论</h3>
<h4 id="11图的简介">1.1.图的简介</h4>
什么是图？
<ul>
<li>图结构是一种与树结构有些相似的数据结构；</li>
<li>图论是数学的一个分支，并且，在数学中，树是图的一种；</li>
<li>图论以图为研究对象，研究顶点和边组成的图形的数学理论和方法；</li>
<li>主要的研究目的为：事物之间的联系，顶点代表事物，边代表两个事物间的关系；</li>
</ul>
图的特点：
<ul>
<li>一组顶点：通常用 V （Vertex）表示顶点的集合；</li>
<li>一组边：通常用 E （Edge）表示边的集合；
<ul>
<li>边是顶点和顶点之间的连线；</li>
<li>边可以是有向的，也可以是无向的。比如A----B表示无向，A ---> B 表示有向；</li>
</ul>
</li>
</ul>
图的常用术语：
<ul>
<li>
顶点：表示图中的一个节点；
</li>
<li>
边：表示顶点和顶点给之间的连线；
</li>
<li>
相邻顶点：由一条边连接在一起的顶点称为相邻顶点；
</li>
<li>
度：一个顶点的度是相邻顶点的数量；
</li>
<li>
路径：
<ul>
<li>简单路径：简单路径要求不包含重复的顶点；</li>
<li>回路：第一个顶点和最后一个顶点相同的路径称为回路；</li>
</ul>
</li>
<li>
无向图：图中的所有边都是没有方向的；
</li>
<li>
有向图：图中的所有边都是有方向的；
</li>
<li>
无权图：无权图中的边没有任何权重意义；
</li>
<li>
带权图：带权图中的边有一定的权重含义；
</li>
</ul>
<h4 id="12图的表示">1.2.图的表示</h4>
<h5 id="邻接矩阵">邻接矩阵</h5>
表示图的常用方式为：邻接矩阵。
<ul>
<li>
可以使用二维数组来表示邻接矩阵；
</li>
<li>
邻接矩阵让每个节点和一个整数相关联，该整数作为数组的下标值；
</li>
<li>
使用一个二维数组来表示顶点之间的连接；
</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%9B%BE/1.png" alt="image-20200303213913574" loading="lazy">
如上图所示：
<ul>
<li>二维数组中的0表示没有连线，1表示有连线；</li>
<li>如：A[ 0 ] [ 3 ] = 1，表示 A 和 C 之间有连接；</li>
<li>邻接矩阵的对角线上的值都为0，表示A - A ，B - B，等自回路都没有连接（自己与自己之间没有连接）；</li>
<li>若为无向图，则邻接矩阵应为对角线上元素全为0的对称矩阵；</li>
</ul>
邻接矩阵的问题：
<ul>
<li>如果图是一个稀疏图，那么邻接矩阵中将存在大量的 0，造成存储空间的浪费；</li>
</ul>
<h5 id="邻接表">邻接表</h5>
另外一种表示图的常用方式为：邻接表。
<ul>
<li>邻接表由图中每个顶点以及和顶点相邻的顶点列表组成；</li>
<li>这个列表可用多种方式存储，比如：数组/链表/字典（哈希表）等都可以；</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%9B%BE/2.png" alt="image-20200303215312091" loading="lazy">
如上图所示：
<ul>
<li>图中可清楚看到A与B、C、D相邻，假如要表示这些与A顶点相邻的顶点（边），可以通过将它们作为A的值（value）存入到对应的数组/链表/字典中。</li>
<li>之后，通过键（key）A可以十分方便地取出对应的数据；</li>
</ul>
邻接表的问题：
<ul>
<li>邻接表可以简单地得出出度，即某一顶点指向其他顶点的个数；</li>
<li>但是，邻接表计算入度（指向某一顶点的其他顶点的个数称为该顶点的入度）十分困难。此时需要构造逆邻接表才能有效计算入度；</li>
</ul>
<h3 id="二封装图结构">二、封装图结构</h3>
在实现过程中采用邻接表的方式来表示边，使用字典类来存储邻接表。
<h4 id="21添加字典类和队列类">2.1.添加字典类和队列类</h4>
首先需要引入之前实现的，之后会用到的字典类和队列类：
<pre><code> //封装字典类
function Dictionary(){
//字典属性
this.items = {}

//字典操作方法
//一.在字典中添加键值对
Dictionary.prototype.set = function(key, value){
this.items = 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
return true
}

//四.根据key获取value
Dictionary.prototype.get = function(key){
return this.has(key) ? this.items : 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
}

// 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
 }
}
</code></pre>
<h4 id="22创建图类">2.2.创建图类</h4>
先创建图类Graph，并添加基本属性，再实现图类的常用方法：
<pre><code> //封装图类
function Graph (){
 //属性：顶点(数组)/边(字典)
 this.vertexes = []//顶点
 this.edges = new Dictionary() //边
 }
</code></pre>
<h4 id="23添加顶点与边">2.3.添加顶点与边</h4>
如图所示：
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%9B%BE/3.png" alt="image-20200303235132868" loading="lazy">
创建一个数组对象vertexes存储图的顶点；创建一个字典对象edges存储图的边，其中key为顶点，value为存储key顶点相邻顶点的数组。
代码实现：
<pre><code> //添加方法
 //一.添加顶点
 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)//表示的是无向表，故要添加互相指向的两条边
 }
</code></pre>
<h4 id="24转换为字符串输出">2.4.转换为字符串输出</h4>
为图类Graph添加toString方法，实现以邻接表的形式输出图中各顶点。
代码实现：
<pre><code> //三.实现toString方法:转换为邻接表形式
 Graph.prototype.toString = function (){
 //1.定义字符串，保存最终结果
 let resultString = ""

 //2.遍历所有的顶点以及顶点对应的边
 for (let i = 0; i < this.vertexes.length; i++) {//遍历所有顶点
 resultString += this.vertexes + '-->'
 let vEdges = this.edges.get(this.vertexes)
 for (let j = 0; j < vEdges.length; j++) {//遍历字典中每个顶点对应的数组
 resultString += vEdges + '';
 }
 resultString += '\n'
 }
 return resultString
 }
</code></pre>
测试代码：
<pre><code> //测试代码
//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)
}

//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());
</code></pre>
测试结果：
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%9B%BE/4.png" alt="image-20200303233737451" loading="lazy">
<h4 id="25图的遍历">2.5.图的遍历</h4>
图的遍历思想：
<ul>
<li>图的遍历思想与树的遍历思想一样，意味着需要将图中所有的顶点都访问一遍，并且不能有重复的访问（上面的toString方法会重复访问）；</li>
</ul>
遍历图的两种算法：
<ul>
<li>广度优先搜索（Breadth - First Search，简称BFS）;</li>
<li>深度优先搜索（Depth - First Search，简称DFS）;</li>
<li>两种遍历算法都需要指定第一个被访问的顶点；</li>
</ul>
为了记录顶点是否被访问过，使用三种颜色来表示它们的状态
<ul>
<li>白色：表示该顶点还没有被访问过；</li>
<li>灰色：表示该顶点被访问过，但其相邻顶点并未完全被访问过；</li>
<li>黑色：表示该顶点被访问过，且其所有相邻顶点都被访问过；</li>
</ul>
首先封装initializeColor方法将图中的所有顶点初始化为白色，代码实现如下：
<pre><code> //四.初始化状态颜色
 Graph.prototype.initializeColor = function(){
 let colors = []
 for (let i = 0; i < this.vertexes.length; i++) {
 colors] = 'white';
 }
 return colors
 }
</code></pre>
<h5 id="广度优先搜索">广度优先搜索</h5>
广度优先搜索算法的思路：
<ul>
<li>广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻顶点，就像一次访问图的一层；</li>
<li>也可以说是先宽后深地遍历图中的各个顶点；</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%9B%BE/5.png" alt="image-20200303233840691" loading="lazy">
实现思路：
基于队列可以简单地实现广度优先搜索算法：
<ul>
<li>首先创建一个队列Q（尾部进，首部出）；</li>
<li>调用封装的initializeColor方法将所有顶点初始化为白色；</li>
<li>指定第一个顶点A，将A标注为灰色（被访问过的节点），并将A放入队列Q中；</li>
<li>循环遍历队列中的元素，只要队列Q非空，就执行以下操作：
<ul>
<li>先将灰色的A从Q的首部取出；</li>
<li>取出A后，将A的所有未被访问过（白色）的相邻顶点依次从队列Q的尾部加入队列，并变为灰色。以此保证，灰色的相邻顶点不重复加入队列；</li>
<li>A的全部相邻节点加入Q后，A变为黑色，在下一次循环中被移除Q外；</li>
</ul>
</li>
</ul>
代码实现：
<pre><code> //五.实现广度搜索(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 = 'gray'

 //4.4.遍历v所有相邻的顶点vNeighbours,并且加入队列中
 for (let i = 0; i < vNeighbours.length; i++) {
 const a = vNeighbours;
 //判断相邻顶点是否被探测过，被探测过则不加入队列中；并且加入队列后变为灰色，表示被探测过
 if (colors == 'white') {
 colors = 'gray'
 que.enqueue(a)
 }
 }

 //4.5.处理顶点v
 handler(v)

 //4.6.顶点v所有白色的相邻顶点都加入队列后，将顶点v设置为黑色。此时黑色顶点v位于队列最前面，进入下一次while循环时会被取出
 colors = 'black'
 }
 }
</code></pre>
过程详解：
下为指定的第一个顶点为A时的遍历过程：
<ul>
<li>如 a 图所示，将在字典edges中取出的与A相邻的且未被访问过的白色顶点B、C、D放入队列que中并变为灰色，随后将A变为黑色并移出队列；</li>
<li>接着，如图 b 所示，将在字典edges中取出的与B相邻的且未被访问过的白色顶点E、F放入队列que中并变为灰色，随后将B变为黑色并移出队列；</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%9B%BE/6.png" alt="image-20200306144336380" loading="lazy">
<ul>
<li>如 c 图所示，将在字典edges中取出的与C相邻的且未被访问过的白色顶点G（A，D也相邻不过已变为灰色，所以不加入队列）放入队列que中并变为灰色，随后将C变为黑色并移出队列；</li>
<li>接着，如图 d 所示，将在字典edges中取出的与D相邻的且未被访问过的白色顶点H放入队列que中并变为灰色，随后将D变为黑色并移出队列。</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%9B%BE/7.png" alt="image-20200306144427242" loading="lazy">
如此循环直到队列中元素为0，即所有顶点都变黑并移出队列后才停止，此时图中顶点已被全部遍历。
测试代码：
<pre><code> //测试代码
//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)
}

//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, function(v){
 result += v + "-"
})
console.log(result);
</code></pre>
测试结果：
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%9B%BE/8.png" alt="image-20200304120023711" loading="lazy">
可见，安装了广度优先搜索的顺序不重复地遍历了所有顶点。
<h5 id="深度优先搜索">深度优先搜索</h5>
广度优先算法的思路：
<ul>
<li>深度优先搜索算法将会从指定的第一个顶点开始遍历图，沿着一条路径遍历直到该路径的最后一个顶点都被访问过为止；</li>
<li>接着沿原来路径回退并探索下一条路径，即先深后宽地遍历图中的各个顶点；</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%9B%BE/9.png" alt="image-20200304120355088" loading="lazy">
实现思路：
<ul>
<li>可以使用栈结构来实现深度优先搜索算法；</li>
<li>深度优先搜索算法的遍历顺序与二叉搜索树中的先序遍历较为相似，同样可以使用递归来实现（递归的本质就是函数栈的调用）。</li>
</ul>
基于递归实现深度优先搜索算法：定义dfs方法用于调用递归方法dfsVisit，定义dfsVisit方法用于递归访问图中的各个顶点。
在dfs方法中：
<ul>
<li>首先，调用initializeColor方法将所有顶点初始化为白色；</li>
<li>然后，调用dfsVisit方法遍历图的顶点；</li>
</ul>
在dfsVisit方法中：
<ul>
<li>首先，将传入的指定节点v标注为灰色；</li>
<li>接着，处理顶点V；</li>
<li>然后，访问V的相邻顶点；</li>
<li>最后，将顶点v标注为黑色；</li>
</ul>
代码实现：
<pre><code> //六.实现深度搜索(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 = 'gray'

 //2.处理v顶点
 handler(v)

 //3.访问V的相邻顶点
 let vNeighbours = this.edges.get(v)
 for (let i = 0; i < vNeighbours.length; i++) {
 let a = vNeighbours;
 //判断相邻顶点是否为白色，若为白色，递归调用函数继续访问
 if (colors == 'white') {
 this.dfsVisit(a, colors, handler)
 }

 }

 //4.将v设置为黑色
 colors = 'black'
 }
</code></pre>
过程详解：
这里主要解释一下代码中的第3步操作：访问指定顶点的相邻顶点。
<ul>
<li>以指定顶点A为例，先从储存顶点及其对应相邻顶点的字典对象edges中取出由顶点A的相邻顶点组成的数组：</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%9B%BE/10.png" alt="image-20200304155916036" loading="lazy">
<ul>
<li>第一步：A顶点变为灰色，随后进入第一个for循环，遍历A白色的相邻顶点：B、C、D；在该for循环的第1次循环中（执行B），B顶点满足：colors == "white"，触发递归，重新调用该方法；</li>
<li>第二步：B顶点变为灰色，随后进入第二个for循环，遍历B白色的相邻顶点：E、F；在该for循环的第1次循环中（执行E），E顶点满足：colors == "white"，触发递归，重新调用该方法；</li>
<li>第三步：E顶点变为灰色，随后进入第三个for循环，遍历E白色的相邻顶点：I；在该for循环的第1次循环中（执行I），I顶点满足：colors == "white"，触发递归，重新调用该方法；</li>
<li>第四步：I顶点变为灰色，随后进入第四个for循环，由于顶点I的相邻顶点E不满足：colors == "white"，停止递归调用。过程如下图所示：</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%9B%BE/11.png" alt="image-20200304160536187" loading="lazy">
<ul>
<li>第五步：递归结束后一路向上返回，首先回到第三个for循环中继续执行其中的第2、3...次循环，每次循环的执行过程与上面的同理，直到递归再次结束后，再返回到第二个for循环中继续执行其中的第2、3...次循环....以此类推直到将图的所有顶点访问完为止。</li>
</ul>
下图为遍历图中各顶点的完整过程：
<ul>
<li>发现表示访问了该顶点，状态变为灰色；</li>
<li>探索表示既访问了该顶点，也访问了该顶点的全部相邻顶点，状态变为黑色；</li>
<li>由于在顶点变为灰色后就调用了处理函数handler，所以handler方法的输出顺序为发现顶点的顺序即：A、B、E、I、F、C、D、G、H 。</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%9B%BE/12.png" alt="image-20200304154745646" loading="lazy">
测试代码：
<pre><code> //测试代码
//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)
}

//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, function(v){
 result += v + "-"
})
console.log(result);

</code></pre>
测试结果：
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%9B%BE/13.png" alt="image-20200304125313739" loading="lazy">
<h4 id="26完整实现">2.6.完整实现</h4>
<pre><code> //封装图结构
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 + '-->'
 let vEdges = this.edges.get(this.vertexes)
 for (let j = 0; j < vEdges.length; j++) {//遍历字典中每个顶点对应的数组
 resultString += vEdges + '';
 }
 resultString += '\n'
 }
 return resultString
 }

 //四.初始化状态颜色
 Graph.prototype.initializeColor = function(){
 let colors = []
 for (let i = 0; i < this.vertexes.length; i++) {
 colors] = '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 = 'gray'

 //4.4.遍历v所有相邻的顶点vNeighbours,并且加入队列中
 for (let i = 0; i < vNeighbours.length; i++) {
 const a = vNeighbours;
 //判断相邻顶点是否被探测过，被探测过则不加入队列中；并且加入队列后变为灰色，表示被探测过
 if (colors == 'white') {
 colors = 'gray'
 que.enqueue(a)
 }
 }

 //4.5.处理顶点v
 handler(v)

 //4.6.顶点v所有白色的相邻顶点都加入队列后，将顶点v设置为黑色。此时黑色顶点v位于队列最前面，进入下一次while循环时会被取出
 colors = '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 = 'gray'

 //2.处理v顶点
 handler(v)

 //3.访问v相连的其他顶点
 let vNeighbours = this.edges.get(v)
 for (let i = 0; i < vNeighbours.length; i++) {
 let a = vNeighbours;
 //判断相邻顶点是否为白色，若为白色，递归调用函数继续访问
 if (colors == 'white') {
 this.dfsVisit(a, colors, handler)
 }

 }

 //4.将v设置为黑色
 colors = 'black'
 }
}
</code></pre>
<blockquote>
参考资料:JavaScript数据结构与算法
</blockquote>

</div>
<div id="MySignature" role="contentinfo">
多抽出1分钟来学习，让你的生命更加精彩！ 
来源：https://www.cnblogs.com/AhuntSun-blog/p/12636692.html

頁: [1]

琼殿技术论坛's Archiver

JavaScript实现图结构