|
图结构 非常得类似我们之前讲到过的树结构，但前者没有很多的从属关系，更多的是各个数据之间的相关联系。在数学的概念中，后者是前者的一种，不过在数据结构中我们还是认为两者有所区别，尽管如此，我们在学习图结构的时候仍可以稍微借鉴一下树结构的思想 这里放上之前树结构的文章地址，没看过的小伙伴可以查阅一下： 【数据结构与算法】详解什么是树结构，并用代码手动实现一个二叉查找树 接下来让我们来一起学习一下图结构吧
数据结构——图结构一、什么是图结构图 是由顶点的集合和边的集合组成的。 在我们的身边有很多用到图结构的地方，例如地铁线路图
其中边是可以有方向的。例如从 二、图结构的术语文章开头说过，图结构与树结构有很多的相似之处，因此我们还是要先来介绍一些下文会提到的图结构中的术语
我们再来看个图的例子，借此来更详细地介绍一下每个术语地含义，如图
邻村表示只需要经过一条边就可以到达另一个村，那么我们就说这两个村互为邻村，也可以称它们互为相邻顶点。每个村都会有一个甚至多个邻村，例如D村的邻村有 A村 、C村 、F村，此时我们就说顶点D（D村）的度为3 假设有一天，你要从A村前往E村，你选择的路线是这样的，如图所示 此时，若你选择的路线是这样的，如图所示
到了晚上，你准备起身回家，但选择经过B村再回家，那么此时你一整天的路线是这样的，如图所示 第二天，你接到一个任务，尽快将一个包裹送往E村，为了节省时间，你查阅资料获取到了各条路的长度，如图所示
通过计算，最后选择了
最后你选择了 三、图的表示上面我们在介绍图的时候，都是用一个形象的图片来讲解的，但在程序中，这样的表达方式显然不是我们想要的，因此我们要找到别的方式来表示结构 图结构的常见的两个表达方式： 邻接矩阵 、邻接表 （1）邻接矩阵顾名思义，邻接矩阵就像数学中的矩阵，我们只不过是借此来表示图结构，如图所示，现在有一个这样的图结构 很明显，该图为无向图，那么我们用矩阵的形式来表示它就如下图 先来看第一行，该行对应的是顶点A，那我们就拿顶点A与其它点一一对应，发现顶点A除了不能通向顶点D和自身，可以通向其它任何一个的顶点 因为该图为无向图，因此顶点A如果能通向另一个顶点，那么这个顶点也一定能通向顶点A，所以这个顶点对应顶点A的也应该是 1 为了大家更好的理解，我根据这个邻接矩阵，重新还原了一幅正确的图结构出来，如下面这张动图所示：
（2）邻接表邻接表 是由每个顶点以及它的相邻顶点组成的 还是使用刚才上面的那个例子，如图
图中最左侧红色的表示各个顶点，它们对应的那一行存储着与它相关联的顶点 因此，我们可以看出：
为了大家更好的理解，我根据这个邻接表，重新还原了一幅正确的图结构出来，如下面这张动图所示：
四、遍历搜索在图结构中，存在着两种遍历搜索的方式，分别是 广度优先搜索 和 深度优先搜索 在介绍这两种搜索方式前，我们先来看一个例子
首先我们可以把它简化成我们学习的图结构，如图
（1）广度优先搜索广度优先搜索 就是从第一个顶点开始，尝试访问尽可能靠近它的顶点，即先访问最靠近它的所有顶点，再访问第二靠近它的所有顶点，以此类推，直到访问完所有的顶点 概念比较抽象，我们就拿上面的例子来说，如图所示
然后再搜索离 再继续往下搜索离 到此为止，整个图结构就已经被遍历完成了，这就是一个广度优先搜索完整的过程 （2）深度优先搜索深度优先搜索 就是从一个顶点开始，沿着一条路径一直搜索，直到到达该路径的最后一个结点，然后回退到之前经过但未搜索过的路径继续搜索，直到所有路径和结点都被搜索完毕 同样的，概念比较抽象，我们来用上面的例子模拟一遍深度优先搜索，如图所示 先随便沿着一条路径一直搜索，图中路径为
当搜索到 此时发现当往后退到 沿着这条路径一直找到了最后一个顶点—— 五、图结构的方法在封装图结构之前，我们先来了解一下图结构都由哪些方法，如下表所示
六、用代码实现图结构前提：
（1）创建一个构造函数首先创建一个大的构造函数，用于存放二叉查找树的一些属性和方法。 function Graph() { // 属性 this.vertexes = [] this.edges = {}}
因为图结构是由顶点的集合和边的集合构成的，因此我们想要设定两个属性 其中，属性 假设我们先新添加一个
（2）实现addVertex()方法
实现思路：
我们来看一下代码 function Graph() { // 属性 this.vertexes = [] this.edges = {}// 方法 // 添加顶点 Graph.prototype.addVertex = function(v) { this.vertexes.push(v) this.edges[v] = [] }}123456789101112123456789101112 我们来使用一下该方法 let graph = new Graph()graph.addVertex(3)graph.addVertex(9)graph.addVertex(5)
我们来看一下我们定义的两个属性是什么样的，如图所示
（3）实现addEdge()方法
实现思路：
我们来看一下代码 function Graph() { // 属性 this.vertexes = [] this.edges = {}// 方法 // 添加边 Graph.prototype.addEdge = function(v1, v2) { this.edges[v1].push(v2) this.edges[v2].push(v1) }}123456789101112123456789101112 现在我们来使用一下该方法 let graph = new Graph()// 向图结构graph.addVertex(3)graph.addVertex(9)graph.addVertex(5)// 为顶点添加边// 在顶点3 和 顶点9 之间添加一条边graph.addEdge(3, 9)// 在顶点3 和 顶点5 之间添加一条边graph.addEdge(3, 5)// 在顶点5 和 顶点9 之间添加一条边graph.addEdge(5, 9)
我们来看一下我们定义的两个属性是什么样的，如图所示
（4）实现toString()方法
我们先来看一下我们最终需要的展示效果是如何的，如图
实现思路：
我们直接来看一下代码 function Graph() { // 属性 this.vertexes = [] this.edges = {}// 方法 // 展示邻接表 Graph.prototype.toString = function() { // 1. 创建字符串，用于存放数据 let string = '' // 2. 遍历所有顶点 for(let i in this.vertexes) {// 2.1 获取遍历到的顶点 let vertex = this.vertexes[i]// 2.2 将遍历到的顶点添加到字符串中 string += `${vertex} => ` // 2.3 获取存储该顶点所有的相邻顶点的数组 let edges = this.edges[vertex]// 2.4 遍历该顶点所有的相邻顶点 for(let i in edges) { // 2.4.1 将遍历到的相邻顶点添加到字符串中 string += `${edges[i]} ` } // 2.5 换行 string += '\n' }// 3. 返回最终结果 return string }}123456789101112131415161718192021222324252627282930313233343536123456789101112131415161718192021222324252627282930313233343536 我们来使用一下该方法，为了方便，这里仍用上面的例子 let graph = new Graph()// 向图结构graph.addVertex(3)graph.addVertex(9)graph.addVertex(5)// 为顶点添加边graph.addEdge(3, 9)graph.addEdge(3, 5)graph.addEdge(5, 9)// 获取邻接表console.log(graph.toString())/* 返回结果为：3 => 9 5 9 => 3 5 5 => 3 9 */
核对了一下，结果时正确的 （5）实现initColor()方法（内部方法）在封装 无论是在进行广度优先搜索还是深度优先搜索时，我们搜索顶点的时候，会频繁地重复搜索到某些顶点，那么我们就要用一种方式，使被搜索过的顶点不再被重复搜索一次。这种方法就是给每个顶点一个颜色标记，没有被搜索过的顶点被标记白色，被搜索过的顶点被标记黑色 我们就拿一个简单的广度优先搜索的例子，来感受一下该方法的作用 首先是广度优先搜索的例子，如图所示
然后接着分别遍历 同样的，当遍历完 所以我们来看一下使用了颜色标记以后的搜索过程吧 首先遍历到初始顶点——
先遍历
这样一个完美的广度优先搜索就完成了。 因此，我们需要封装一个颜色初始化的函数，用于将所有顶点的颜色都初始化为白色，并将颜色信息存放在一个对象中，返回该对象用于别的函数 我们来看一下代码 function Graph() { // 属性 this.vertexes = [] this.edges = {}// 方法 // 顶点颜色初始化（内部函数） Graph.prototype.initColor = function() { // 1. 创建对象，存放颜色信息 let color = {} // 2. 遍历所有顶点，将其颜色初始化为白色 for(let i in this.vertexes) { color[this.vertexes[i]] = 'white' }// 3. 返回颜色对象 return color }}12345678910111213141516171819201234567891011121314151617181920 该方法的使用我们会在后续使用到，这里就不做演示了 （6）实现breadthFirstSearch()方法
在上文多次介绍了广度优先搜索，其实这是一种基于队列来搜索顶点的方式 注： 这里我就把我之前文章中封装的队列构造函数直接拿来使用了，如果想看队列的各个方法的实现过程的小伙伴可以点击下面跳转链接进行查看 【数据结构与算法】详解什么是队列，并用代码手动实现一个队列结构 实现思路：
我们来看一下具体的代码 function Graph() { // 属性 this.vertexes = [] this.edges = {}// 已经封装好的队列构造函数function Queue() { this.list = [] //入队列 Queue.prototype.enqueue = function (e) { this.list.push(e) } //出队列 Queue.prototype.dequeue = function () { return this.list.shift() } //判断队列是否为空 Queue.prototype.isEmpty = function() { if(this.list.length === 0) { return true } else { return false } } //返回队列中元素个数 Queue.prototype.size = function () { return this.list.length } //返回队列中的第一个元素 Queue.prototype.front = function () { return this.list[0] } //返回当前队列 Queue.prototype.toString = function () { let string = '' for(let i in this.list) { string += `${this.list[i]} ` } return string }}// 方法 // 顶点颜色初始化（内部函数） Graph.prototype.initColor = function() { // 1. 创建对象，存放颜色信息 let color = {} // 2. 遍历所有顶点，将其颜色初始化为白色 for(let i in this.vertexes) { color[this.vertexes[i]] = 'white' }// 3. 返回颜色对象 return color }// 广度优先搜索 Graph.prototype.breadthFirstSearch = function(firstVertex, handle) { // 1. 初始化所有顶点颜色 const color = this.initColor() // 2. 新建一个队列 const queue = new Queue() // 3. 将第一个顶点加入队列 queue.enqueue(firstVertex) // 4. 开始广度优先搜索 while(!queue.isEmpty()) { // 4.1 从队列中取出一个顶点 let vertex = queue.dequeue() // 4.2 获取与该顶点相关的其他顶点 let otherVertexes = this.edges[vertex] // 4.3 将该顶点设为黑色，表示已被访问过，防止后面重复访问 color[vertex] = 'black' // 4.4 遍历与该顶点相关的其它顶点 for(let i in otherVertexes) { // 4.4.1 获取与该顶点相关的顶点 let item = otherVertexes[i] // 4.4.1 若未被访问，则加入到队列中 if(color[item] === 'white') { color[item] = 'black' queue.enqueue(item) } } // 4.5 执行我们的回调函数 handle(vertex) } }}
我们来使用一下该方法吧，为了方便检查函数的正确性，我们之前介绍到的吃金币的例子，并且回调函数 这里我直接把正确的访问顺序图放在这里，方便大家下面核对结果是否正确 let graph = new Graph()graph.addVertex(1)graph.addVertex(2)graph.addVertex(3)graph.addVertex(4)graph.addVertex(5)graph.addVertex(6)graph.addVertex(7)graph.addVertex(8)graph.addVertex(9)graph.addEdge(1, 2)graph.addEdge(1, 7)graph.addEdge(2, 3)graph.addEdge(2, 5)graph.addEdge(3, 2)graph.addEdge(3, 6)graph.addEdge(4, 5)graph.addEdge(5, 4)graph.addEdge(5, 2)graph.addEdge(5, 8)graph.addEdge(6, 3)graph.addEdge(6, 9)graph.addEdge(7, 1)graph.addEdge(7, 8)graph.addEdge(8, 5)graph.addEdge(8, 7)graph.addEdge(8, 9)graph.addEdge(9, 6)graph.addEdge(9, 8)// 广度优先搜索graph.breadthFirstSearch(1, function(vertex) {// 打印访问到的顶点console.log(vertex)})/* 打印结果：127358649*/123456789101112131415161718192021222324252627282930313233343536373839404142434445464748123456789101112131415161718192021222324252627282930313233343536373839404142434445464748 把打印的结果和图片核对以后发现结果是一致的，因此这个方法是没有问题的 （7）实现depthFirstSearch()方法
在上文多次介绍了深度优先搜索，其实这是一种基于栈来搜索顶点的方式，我们也直到其实递归也是利用栈结构的思路实现的，因此我们这里封装该方法时就不把之前封装好的栈结构拿来使用了，直接利用递归实现，正好递归也能把代码变得简洁点 因此首先我们要封装一个递归调用的主体函数，方法名为 depthVisit()方法的实现思路：
再来简单说一下 depthFirstSearch()方法的实现思路：
接下来我们来看一下具体的代码吧 function Graph() { // 属性 this.vertexes = [] this.edges = {}// 方法 // 顶点颜色初始化（内部函数） Graph.prototype.initColor = function() { // 1. 创建对象，存放颜色信息 let color = {} // 2. 遍历所有顶点，将其颜色初始化为白色 for(let i in this.vertexes) { color[this.vertexes[i]] = 'white' }// 3. 返回颜色对象 return color }// 深度优先搜索 Graph.prototype.depthFirstSearch = function(firstVertex, handle) { // 1. 初始化所有顶点颜色 const color = this.initColor() // 2. 开始递归访问各个顶点 this.depthVisit(firstVertex, color, handle) } // 深度优先搜索的递归访问（内部函数） Graph.prototype.depthVisit = function(vertex, color, handle) { // 1. 先将访问到的顶点颜色设为黑色，防止后面重复访问 color[vertex] = 'black' // 2. 执行回调函数 handle(vertex) // 3. 获取与该顶点相关的其它顶点 let otherVertexes = this.edges[vertex] // 4. 遍历所有相关的顶点 for(let i in otherVertexes) { let item = otherVertexes[i] // 4.1 访问没有被访问过的相邻顶点 if(color[item] === 'white') { this.depthVisit(item, color, handle) } } }}
同样的，我们也用上文将到的吃金币例子中的深度优先搜索的结果图来验证我们方法的正确性，图片如下
let graph = new Graph()graph.addVertex(1)graph.addVertex(2)graph.addVertex(3)graph.addVertex(4)graph.addVertex(5)graph.addVertex(6)graph.addVertex(7)graph.addVertex(8)graph.addVertex(9)graph.addEdge(1, 2)graph.addEdge(1, 7)graph.addEdge(2, 3)graph.addEdge(2, 5)graph.addEdge(3, 2)graph.addEdge(3, 6)graph.addEdge(4, 5)graph.addEdge(5, 4)graph.addEdge(5, 2)graph.addEdge(5, 8)graph.addEdge(6, 3)graph.addEdge(6, 9)graph.addEdge(7, 1)graph.addEdge(7, 8)graph.addEdge(8, 5)graph.addEdge(8, 7)graph.addEdge(8, 9)graph.addEdge(9, 6)graph.addEdge(9, 8)// 深度优先搜索graph.depthFirstSearch(1, function(vertex) {// 打印访问到的顶点console.log(vertex)})/* 打印结果：123698547*/123456789101112131415161718192021222324252627282930313233343536373839404142434445464748123456789101112131415161718192021222324252627282930313233343536373839404142434445464748 把打印的结果和图片核对以后发现结果是一致的，因此这个方法是没有问题的 七、结束语图结构的讲解就到这里了，希望大家对图结构有了更深一层的理解。到此为止，我的【数据结构与算法】专栏中的数据结构部分已经结束了，接下来准备开始讲解排序算法了，下一篇文章为基本排序算法，顺便会在文中介绍一下大O表示法。 大家可以关注我，之后我还会一直更新别的数据结构与算法的文章来供大家学习，并且我会把这些文章放到【数据结构与算法】这个专栏里，供大家学习使用。 |
|
|
