精华内容
下载资源
问答
  • 图结构 非常得类似我们之前讲到过的树结构,但前者没有很多的从属关系,更多的是各个数据之间的相关联系。在数学的概念中,后者是前者的一种,不过在数据结构中我们还是认为两者有所区别,尽管如此,我们在学习...

    本系列文章【数据结构与算法】所有完整代码已上传 github,想要完整代码的小伙伴可以直接去那获取,可以的话欢迎点个Star哦~下面放上跳转链接

    图结构 非常得类似我们之前讲到过的树结构,但前者没有很多的从属关系,更多的是各个数据之间的相关联系。在数学的概念中,后者是前者的一种,不过在数据结构中我们还是认为两者有所区别,尽管如此,我们在学习图结构的时候仍可以稍微借鉴一下树结构的思想

    这里放上之前树结构的文章地址,没看过的小伙伴可以查阅一下:

    【数据结构与算法】详解什么是树结构,并用代码手动实现一个二叉查找树

    接下来让我们来一起学习一下图结构吧

    在这里插入图片描述

    • 公众号:前端印象
    • 不定时有送书活动,记得关注~
    • 关注后回复对应文字领取:【面试题】、【前端必看电子书】、【数据结构与算法完整代码】、【前端技术交流群】

    一、什么是图结构

    是由顶点的集合和边的集合组成的。

    在我们的身边有很多用到图结构的地方,例如地铁线路图

    在这里插入图片描述
    地铁线路图中每一个站点都可以看成一个顶点,而连接着每个站点的线路可以看作是

    其中是可以有方向的。例如从 站点1站点2 是可以的,但是反过来 站点2站点1 是不可以的,那么此时就说 顶点1顶点2 之间的边是有方向的,方向为 顶点1 -> 顶点2

    二、图结构的术语

    文章开头说过,图结构与树结构有很多的相似之处,因此我们还是要先来介绍一些下文会提到的图结构中的术语

    术语含义
    顶点图中的某个结点
    顶点之间连线
    相邻顶点由同一条边连接在一起的顶点
    一个顶点的相邻顶点个数
    简单路径由一个顶点到另一个顶点的路线,且没有重复经过顶点
    回路第一个顶点和最后一个顶点的相同的路径
    无向图图中所有的边都没有方向
    有向图图中所有的边都有方向
    无权图图中的边没有权重值
    有权图图中的边带有一定的权重值

    我们再来看个图的例子,借此来更详细地介绍一下每个术语地含义,如图

    在这里插入图片描述
    该图为某某县地村落分布图,我们可以把其看成是一个图结构,其中每个村看成是一个顶点,每两个村之间可能通了一条路方便来往,例如 A村和D村之间就有一条路线1,我们称之为

    邻村表示只需要经过一条边就可以到达另一个村,那么我们就说这两个村互为邻村,也可以称它们互为相邻顶点。每个村都会有一个甚至多个邻村,例如D村的邻村有 A村 、C村 、F村,此时我们就说顶点D(D村)的为3

    假设有一天,你要从A村前往E村,你选择的路线是这样的,如图所示
    在这里插入图片描述
    途中我们经过了 顶点A顶点C顶点E ,没有重复经过某个顶点,因此我们称这条路线为简单路径

    此时,若你选择的路线是这样的,如图所示

    在这里插入图片描述
    途中经过两次 顶点C ,此时我们就不能称这条路线为简单路径了

    到了晚上,你准备起身回家,但选择经过B村再回家,那么此时你一整天的路线是这样的,如图所示
    在这里插入图片描述
    因为你当前的出发点和结束点都是A村(顶点A),因此这样的路线我们称之为回路

    第二天,你接到一个任务,尽快将一个包裹送往E村,为了节省时间,你查阅资料获取到了各条路的长度,如图所示

    在这里插入图片描述
    此时的图结构上每条边就带上了权重值,我们称这个图为有权图

    通过计算,最后选择了 A村 -> C村 -> E村 这条路线,等到包裹送到E村以后,你正准备原路返回,但发现来时的路都是单向的,现在不允许走这条路回去了,于是你又查阅资料,查看这个县各条路的方向情况,结果如图所示

    在这里插入图片描述
    此时的图结构上每条边都有一定的方向,我们称这个图为有向图

    最后你选择了 E村 -> B村 -> A村 这条路线成功回到了家

    三、图的表示

    上面我们在介绍图的时候,都是用一个形象的图片来讲解的,但在程序中,这样的表达方式显然不是我们想要的,因此我们要找到别的方式来表示结构

    图结构的常见的两个表达方式: 邻接矩阵邻接表

    (1)邻接矩阵

    顾名思义,邻接矩阵就像数学中的矩阵,我们只不过是借此来表示图结构,如图所示,现在有一个这样的图结构

    在这里插入图片描述

    很明显,该图为无向图,那么我们用矩阵的形式来表示它就如下图
    在这里插入图片描述
    图中的 0 表示该顶点无法通向另一个顶点,相反 1 就表示该顶点能通向另一个顶点

    先来看第一行,该行对应的是顶点A,那我们就拿顶点A与其它点一一对应,发现顶点A除了不能通向顶点D和自身,可以通向其它任何一个的顶点

    因为该图为无向图,因此顶点A如果能通向另一个顶点,那么这个顶点也一定能通向顶点A,所以这个顶点对应顶点A的也应该是 1

    为了大家更好的理解,我根据这个邻接矩阵,重新还原了一幅正确的图结构出来,如下面这张动图所示:

    在这里插入图片描述
    虽然我们确实用邻接矩阵表示了图结构,但是它有一个致命的缺点,那就是矩阵中存在着大量的0,这在程序中会占据大量的内存。此时我们思考一下,0就是表示没有,没有为什么还要写,所以我们来看一下第二种表示图结构的方法,它就很好的解决了邻接矩阵的缺陷

    (2)邻接表

    邻接表 是由每个顶点以及它的相邻顶点组成的

    还是使用刚才上面的那个例子,如图

    在这里插入图片描述
    那么此时我们的邻接表就是这样的,如下图

    在这里插入图片描述

    图中最左侧红色的表示各个顶点,它们对应的那一行存储着与它相关联的顶点

    因此,我们可以看出:

    • 顶点A 与 顶点B顶点C顶点E 相关联
    • 顶点B 与 顶点A 相关联
    • 顶点C 与 顶点A顶点D顶点E 相关联
    • 顶点D 与 顶点C 相关联
    • 顶点E 与 顶点A顶点C 相关联

    为了大家更好的理解,我根据这个邻接表,重新还原了一幅正确的图结构出来,如下面这张动图所示:

    在这里插入图片描述
    我们在文章末尾封装图结构时,也会用到这种表示方法

    四、遍历搜索

    在图结构中,存在着两种遍历搜索的方式,分别是 广度优先搜索深度优先搜索

    在介绍这两种搜索方式前,我们先来看一个例子

    在这里插入图片描述
    这是一个吃金币的小游戏,从入口开始,进去吃掉所到所有的金币,但是要尽可能少得走重复的路

    首先我们可以把它简化成我们学习的图结构,如图

    在这里插入图片描述
    接下来我们就根据这个图结构来介绍两种遍历搜索方式

    (1)广度优先搜索

    广度优先搜索 就是从第一个顶点开始,尝试访问尽可能靠近它的顶点,即先访问最靠近它的所有顶点,再访问第二靠近它的所有顶点,以此类推,直到访问完所有的顶点

    概念比较抽象,我们就拿上面的例子来说,如图所示

    在这里插入图片描述
    第一次先搜索离 顶点1 最近的两个顶点,即 顶点2顶点7

    然后再搜索离 顶点1 第二近的所有顶点,也就是离 顶点2顶点7 最近的所有顶点,如图所示
    在这里插入图片描述
    由图可知,离顶点2 最近的顶点为 顶点3顶点5 ,离 顶点7 最近的顶点为 顶点8 ,因此这几个点以此被遍历

    再继续往下搜索离 顶点1 第三近的所有顶点,也就是离 顶点3顶点5顶点8 最近的所有顶点,搜索过程如图所示
    在这里插入图片描述
    由图可知,离 顶点3 最近的顶点有 顶点6 ;离 顶点5 最近的顶点有 顶点4 ;离 顶点8 最近的顶点有 顶点9,因此它们也逐一被遍历

    到此为止,整个图结构就已经被遍历完成了,这就是一个广度优先搜索完整的过程

    (2)深度优先搜索

    深度优先搜索 就是从一个顶点开始,沿着一条路径一直搜索,直到到达该路径的最后一个结点,然后回退到之前经过但未搜索过的路径继续搜索,直到所有路径和结点都被搜索完毕

    同样的,概念比较抽象,我们来用上面的例子模拟一遍深度优先搜索,如图所示

    先随便沿着一条路径一直搜索,图中路径为 1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 5 -> 4

    在这里插入图片描述

    当搜索到 顶点4 时,发现查找不到未被访问的顶点了,因此 顶点4 就是这条路径的最后一个顶点,此时我们要往后倒退,找寻别的每搜索过的路径

    此时发现当往后退到 顶点8 时,有一条路径上还有未被搜索过的顶点,即 8 -> 7 ,如图所示
    在这里插入图片描述

    沿着这条路径一直找到了最后一个顶点—— 顶点7,此时我们要继续往后退,看看还有没有别的路径没走过并且有未搜索过的顶点,但此时发现所有顶点都被访问过了,因此一个完整的深度优先搜索就完成了

    五、图结构的方法

    在封装图结构之前,我们先来了解一下图结构都由哪些方法,如下表所示

    方法含义
    addVertex()添加顶点
    addEdge()添加边
    toString()展示邻接表
    breadthFirstSearch()广度优先搜索
    depthFirstSearch()深度优先搜索

    六、用代码实现图结构

    前提:

    1. 我们封装的图结构中,存储边的方式用到的是我们上文提到的邻接表
    2. 封装的图结构面向的都是无权无向图

    (1)创建一个构造函数

    首先创建一个大的构造函数,用于存放二叉查找树的一些属性和方法。

    function Graph() {
        // 属性
        this.vertexes = []
        this.edges = {}
    }
    

    因为图结构是由顶点的集合和边的集合构成的,因此我们想要设定两个属性 vertexesedges ,分别存储着所有的顶点 、所有的边

    其中,属性 edges 是初始化了一个空对象。

    假设我们先新添加一个 顶点A ,那么我们除了在属性 vertexes 中存储一下该顶点信息,我们还要为 顶点A 在属性 edges 中创建一个键值对,键为 顶点A ,值是一个空数组,用于存放之后它的相邻顶点,如图所示

    在这里插入图片描述
    然后我们又新添加一个 顶点B ,并且设定 顶点A顶点B 为相邻顶点,那么此时的属性 edges 是这样的

    在这里插入图片描述
    此时可以很明显的看出,顶点A顶点B 相关联,即它们之间有一条边,它们互为相邻顶点

    (2)实现addVertex()方法

    addVertex() 方法就是将一个顶点添加到图结构中。该方法需要传入一个参数 v 用于表示顶点信息

    实现思路:

    1. 将新添加的顶点 v 添加到属性 vertexes
    2. 在属性 edges 中为顶点 v 创建一个数组空间,用于存放与其相关的边的信息

    我们来看一下代码

    function Graph() {
        // 属性
        this.vertexes = []
        this.edges = {}
    
    	// 方法
        // 添加顶点
        Graph.prototype.addVertex = function(v) {
            this.vertexes.push(v)
            this.edges[v] = []
        }
    }
    

    我们来使用一下该方法

    let graph = new Graph()
    
    graph.addVertex(3)
    graph.addVertex(9)
    graph.addVertex(5)
    

    我们来看一下我们定义的两个属性是什么样的,如图所示

    在这里插入图片描述

    在这里插入图片描述
    此时的各个顶点之间是没有任何的边的,等我们后面封装好了添加边的方法以后,再回头来看一下

    (3)实现addEdge()方法

    addEdge() 方法用于向图结构中添加边。该方法需要传入两个参数,即 v1v2,分别代表两个顶点

    实现思路:

    1. 找到属性 edges 中的 v1,为其添加一个相邻顶点 v1
    2. 同时找到属性 edges 中的 v2,为其添加一个相邻顶点 v1

    我们来看一下代码

    function Graph() {
        // 属性
        this.vertexes = []
        this.edges = {}
    
    	// 方法
        // 添加边
        Graph.prototype.addEdge = function(v1, v2) {
            this.edges[v1].push(v2)
            this.edges[v2].push(v1)
        }
    }
    

    现在我们来使用一下该方法

    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()方法

    toString() 方法是用字符串的形式来向我们展示邻接表。该方法无需传入参数

    我们先来看一下我们最终需要的展示效果是如何的,如图

    在这里插入图片描述
    其实就是依次展示了每个顶点的所有相邻顶点

    实现思路:

    1. 创建一个字符串 str
    2. 遍历属性 vertexes,获取到每个顶点
    3. 每获取到一个顶点时,添加到 str 中,然后从属性 edges 中找到存放该顶点的相邻顶点的数组,然后遍历该数组,将所有相邻顶点添加到 str
    4. 最终返回 str

    我们直接来看一下代码

    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
        }
    }
    

    我们来使用一下该方法,为了方便,这里仍用上面的例子

    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()方法(内部方法)

    在封装 breadthFirstSearch()方法和 depthFirstSearch() 方法之前,我们要额外封装一个 initColor()方法,这里要用到一个思想,但上面在介绍广度优先搜索和深度优先搜索时没有提到,这里我们来了解一下

    无论是在进行广度优先搜索还是深度优先搜索时,我们搜索顶点的时候,会频繁地重复搜索到某些顶点,那么我们就要用一种方式,使被搜索过的顶点不再被重复搜索一次。这种方法就是给每个顶点一个颜色标记,没有被搜索过的顶点被标记白色,被搜索过的顶点被标记黑色

    我们就拿一个简单的广度优先搜索的例子,来感受一下该方法的作用

    首先是广度优先搜索的例子,如图所示

    在这里插入图片描述
    首先我们从 顶点A 开始搜索,先依次遍历其所有的相邻顶点有 顶点B顶点C

    然后接着分别遍历 顶点B顶点C 的所有相邻顶点,其中 顶点B 的所有相邻顶点有 顶点A顶点C顶点D顶点C 的所有相邻顶点有 顶点A顶点B顶点D ,我们就按上述顺序依次遍历。此时我们可以发现,当遍历 顶点B 的相邻顶点时,会搜索到 顶点A,但是 顶点A 是我们一开始就搜索过的,因此不应该重复遍历。

    同样的,当遍历完 顶点B 的相邻顶点以后,在遍历 顶点C 的相邻顶点时,我们会发现其所有的相邻顶点之前都已经搜索过了,现在不应该重复遍历了。

    所以我们来看一下使用了颜色标记以后的搜索过程吧

    首先遍历到初始顶点——顶点A,此时我们给它标记黑色

    在这里插入图片描述
    接着遍历 顶点A 所有的相邻顶点,即 顶点B顶点C,并将它们都标记为黑色

    在这里插入图片描述
    最后,我们要遍历 顶点B顶点C 所有的相邻顶点

    先遍历 顶点B 的相邻顶点,分别是 顶点A顶点C顶点D,我们通过颜色辨认得知 顶点A顶点C 都为黑色,表示已经被搜索过了,所以无需重复遍历它们,此时只有 顶点D 不为黑色,所以我们搜索到了 顶点D,并将其标记为黑色

    在这里插入图片描述
    接着我们要遍历 顶点C 的相邻顶点,分别为 顶点A顶点B顶点D,但我们此时通过颜色辨认发现,所有的相邻顶点都被搜索过了,因此无需重复遍历这些顶点了。

    这样一个完美的广度优先搜索就完成了。

    因此,我们需要封装一个颜色初始化的函数,用于将所有顶点的颜色都初始化为白色,并将颜色信息存放在一个对象中,返回该对象用于别的函数

    我们来看一下代码

    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       
        }
    }
    

    该方法的使用我们会在后续使用到,这里就不做演示了

    (6)实现breadthFirstSearch()方法

    breadthFirstSearch() 方法是对图结构进行广度优先搜索。该方法接收两个参数,第一个参数为初始顶点,即从哪个顶点开始搜索;第二个参数接收一个回调函数 handle 作为参数,用于在搜索过程中进行一些操作

    在上文多次介绍了广度优先搜索,其实这是一种基于队列来搜索顶点的方式

    注: 这里我就把我之前文章中封装的队列构造函数直接拿来使用了,如果想看队列的各个方法的实现过程的小伙伴可以点击下面跳转链接进行查看

    【数据结构与算法】详解什么是队列,并用代码手动实现一个队列结构

    实现思路:

    1. 先将所有的顶点颜色初始化为白色
    2. 从给定的第一个顶点开始搜索,即将第一个顶点添加到队列中,并将第一个顶点标记为黑色
    3. 从队列中取出一个顶点,查找该顶点的未被访问过的相邻顶点,将其添加到队列的队尾位置,并将这些顶点标记未黑色,表示也被访问过
    4. 执行我们的回调函数 handle,将该顶点作为参数传入
    5. 一直循环 步骤3 ~ 步骤4 ,直到队列为空

    我们来看一下具体的代码

    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)
            }     
        }
    }
    

    我们来使用一下该方法吧,为了方便检查函数的正确性,我们之前介绍到的吃金币的例子,并且回调函数 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.breadthFirstSearch(1, function(vertex) {
    	// 打印访问到的顶点
    	console.log(vertex)
    })
    /* 打印结果:
    			1
    			2
    			7
    			3
    			5
    			8
    			6
    			4
    			9
    */
    

    把打印的结果和图片核对以后发现结果是一致的,因此这个方法是没有问题的

    (7)实现depthFirstSearch()方法

    depthFirstSearch() 方法是对图结构进行深度优先搜索。该方法接收两个参数,第一个参数为初始顶点,即从哪个顶点开始搜索;第二个参数接收一个回调函数 handle 作为参数,用于在搜索过程中进行一些操作

    在上文多次介绍了深度优先搜索,其实这是一种基于来搜索顶点的方式,我们也直到其实递归也是利用栈结构的思路实现的,因此我们这里封装该方法时就不把之前封装好的栈结构拿来使用了,直接利用递归实现,正好递归也能把代码变得简洁点

    因此首先我们要封装一个递归调用的主体函数,方法名为 depthVisit,该方法接收三个参数,第一个参数为搜索的顶点;第二个参数为存储顶点颜色信息的对象;第三个参数为回调函数,实现思路如下

    depthVisit()方法的实现思路:

    1. 从给定的顶点开始搜索,将其标记为黑色,表示已被访问过
    2. 执行我们的回调函数 handle,将该顶点作为参数传入
    3. 遍历该顶点的所有相邻顶点,若相邻顶点为黑色,则表示已被访问过,就不做任何处理
    4. 若相邻顶点为白色,则表示未被访问,于是就再次调用 breadthFirstSearch()方法,将该顶点作为第一个参数

    再来简单说一下 depthFirstSearch() 方法的实现思路

    depthFirstSearch()方法的实现思路:

    1. 将所有顶点的颜色初始化为白色
    2. 选择一个顶点作为深度优先搜索的第一个顶点,调用 depthVisit()方法,并将该顶点作为该方法的第一个参数

    接下来我们来看一下具体的代码吧

    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)
    })
    /* 打印结果:
    			1
    			2
    			3
    			6
    			9
    			8
    			5
    			4
    			7
    */
    

    把打印的结果和图片核对以后发现结果是一致的,因此这个方法是没有问题的

    七、结束语

    图结构的讲解就到这里了,希望大家对图结构有了更深一层的理解。到此为止,我的【数据结构与算法】专栏中的数据结构部分已经结束了,接下来准备开始讲解排序算法了,下一篇文章为基本排序算法,顺便会在文中介绍一下大O表示法

    大家可以关注我,之后我还会一直更新别的数据结构与算法的文章来供大家学习,并且我会把这些文章放到【数据结构与算法】这个专栏里,供大家学习使用。

    然后大家可以关注一下我的微信公众号:前端印象,等这个专栏的文章完结以后,我会把每种数据结构和算法的笔记放到公众号上,大家可以去那获取。

    或者也可以去我的github上获取完整代码,欢迎大家点个Star

    我是Lpyexplore,创作不易,喜欢的加个关注,点个收藏,给个赞~ 带你们在Python爬虫的过程中学习Web前端

    展开全文
  • 在页面中如何用js或者插件生成多叉树状图结构,就像这样: ![图片说明](https://img-ask.csdn.net/upload/201711/17/1510904545_634368.png)
  • 图结构的python实现

    万次阅读 2018-11-18 18:16:12
    本文主要介绍两种基于python的图结构的实现方法。 邻接矩阵实现 邻接矩阵是表示图中顶点间邻接关系的方阵。对于n个顶点的图G=(V,E),其邻接矩阵是一个的方阵,图中每个顶点(按顺序)对应于矩阵里的一行和一列,...

    图是一种非线性的关系型数据结构,关于图的概念以及性质网络上已有很多资料,我不再多说。本文主要介绍两种基于python的图结构的实现方法。

    邻接矩阵实现

    邻接矩阵是表示图中顶点间邻接关系的方阵。对于n个顶点的图G=(V,E),其邻接矩阵是一个n\times n的方阵,图中每个顶点(按顺序)对应于矩阵里的一行和一列,矩阵元素表示图中的邻接关系。一般对于不带权值的图,用1表示节点有边,用0表示节点无边。

    对于有权图,矩阵元素值即为边的权值,可用0或\infty表示两顶点不相连。显然,对于无向图,其邻接矩阵是一个对称矩阵。

    如上图所示连个图的邻接矩阵分别为 

       A_{G5}=\begin{pmatrix} 0& 0& 1\\ 1& 0& 1\\ 0& 1& 0 \end{pmatrix}  A_{G6}=\begin{pmatrix} 0& 1& 1& 0\\ 1& 0& 1& 0\\ 1& 1& 0& 1\\ 0& 0& 1& 0 \end{pmatrix}

    其中a,b,c的行下标分别为0,1,2。

    在python中实现的代码:

    class Graph:
        def __init__(self,mat,unconn=0):
            vnum=len(mat)
            for x in mat:
                if len(x)!=vnum:
                    raise ValueError("参数错误")
            self._mat=[mat[i][:] for i in range(vnum)]  #做拷贝
            self._unconn=unconn
            self._vnum=vnum
    
        #顶点个数
        def vertex_num(self):
            return self._vnum
    
        #顶点是否无效
        def _invalid(self,v):
            return v<0 or v>=self._vnum
    
        #添加边
        def add_edge(self,vi,vj,val=1):
            if self._invalid(vi) or self._invalid(vj):
                raise ValueError(str(vi)+" or "+str(vj)+"不是有效的顶点")
            self._mat[vi][vj]=val
    
        #获取边的值
        def get_edge(self,vi,vj):
            if self._invalid(vi) or self._invalid(vj):
                raise ValueError(str(vi)+" or "+str(vj)+"不是有效的顶点")
            return self._mat[vi][vj]
    
        #获得一个顶点的各条出边
        def out_edges(self,vi):
            if self._invalid(vi):
                raise ValueError(str(vi)+"不是有效的顶点")
            return self._out_edges(self._mat[vi],self._unconn)
    
        @staticmethod
        def _out_edges(row,unconn):
            edegs=[]
            for i in range(len(row)):
                if row[i]!=unconn:
                    edegs.append((i,row[i]))
            return edegs
    
        def __str__(self):
            return "[\n"+",\n".join(map(str,self._mat))+"\n]"+"\nUnconnected: "+str(self._unconn)

     邻接矩阵存储在mat中,是一个二层嵌套的列表。注意到,该图类没有定义添加顶点的操作,主要是因为添加顶点时,要横向和纵向扩充邻接矩阵,操作不便。

    可见用邻接矩阵表示图的方式所需的空间开销是和图的顶点数的平方成正比的,如果图的顶点数比较多,并且图的每个顶点的度并不多,这样邻接矩阵就是一个稀疏矩阵,其中大部分元素都是无用的,反而耗费了大量的存储空间。另外,也不便添加顶点。

    邻接表实现 

    所谓邻接表,就是为图中每个顶点关联一个边表,其中记录这个顶点的所有邻接边。这样,一个顶点的表,其中每个顶点又关联一个边表,就构成了图的一种表示。如下图,右图是左图的邻接表表示,但没有表示权值。

     

     以下是在python中的实现:

    class GraphAL(Graph):
        def __init__(self,mat=[],unconn=0):
            vnum = len(mat)
            for x in mat:
                if len(x) != vnum:
                    raise ValueError("参数错误")
            self._mat=[Graph._out_edges(mat[i],unconn) for i in range(vnum)]
            self._unconn = unconn
            self._vnum = vnum
    
        #添加顶点
        #返回该顶点编号
        def add_vertex(self):
            self._mat.append([])
            self._vnum+=1
            return self._vnum-1
    
        #添加边
        def add_edge(self,vi,vj,val=1):
            if self._vnum==0:
                raise ValueError("不能向空图添加边")
            if self._invalid(vi) or self._invalid(vj):
                raise ValueError(str(vi)+" or "+str(vj)+"不是有效的顶点")
    
            row=self._mat[vi]
            i=0
            while i<len(row):
                if row[i][0]==vj:
                    self._mat[vi][i]=(vj,val)   #如果原来有到vj的边,修改mat[vi][vj]的值
                    return
                if row[i][0]>vj:    #原来没有到vj的边,退出循环后加入边
                    break
                i+=1
            self._mat[vi].insert(i,(vj,val))
    
        #获取边的值
        def get_edge(self,vi,vj):
            if self._invalid(vi) or self._invalid(vj):
                raise ValueError(str(vi)+" or "+str(vj)+"不是有效的顶点")
            for i,val in self._mat[vi]:
                if i==vj:
                    return val
            return self._unconn
    
        # 获得一个顶点的各条出边
        def out_edges(self,vi):
            if self._invalid(vi):
                raise ValueError(str(vi)+"不是有效的顶点")
            return self._mat[vi]

     可以,这种表示图的方式更加节省空间,且插入顶点操作比较简单。但由于每个顶点的边表的元素是按终点的编号排序的,因此在插入边时,需要从头遍历该列表,在一定程度上增加了算法的复杂度。

    展开全文
  • 数据结构:图结构的实现

    万次阅读 多人点赞 2018-02-07 19:44:45
    是一种很重要的数据结构,不解释。

    数据结构:图结构的实现

    图(Graph)是由顶点和连接顶点的边构成的离散结构。在计算机科学中,图是最灵活的数据结构之一,很多问题都可以使用图模型进行建模求解。例如:生态环境中不同物种的相互竞争、人与人之间的社交与关系网络、化学上用图区分结构不同但分子式相同的同分异构体、分析计算机网络的拓扑结构确定两台计算机是否可以通信、找到两个城市之间的最短路径等等。

    额,我都不研究这些问题。之所以重新回顾数据结构,仅仅是为了好玩。图(Graph)通常会放在树(Tree)后面介绍,树可以说只是图的特例,但是我觉得就基础算法而言,树比图复杂很多,而且听起来也没什么好玩的(左左旋、左右旋、右右旋、右左旋,好无聊~)。因此,我写的第一篇数据结构的笔记就从图开始。

    1 图的概念

    1.1 图的基础概念串讲

    图的结构很简单,就是由顶点 V V V 集和边 E E E 集构成,因此图可以表示成 G = ( V , E ) G=(V, E) G=(V,E)
    图1-1:无向图
    图1-1:无向图1

    图1-1就是无向图,我们可以说这张图中,有点集 V = { 1 , 2 , 3 , 4 , 5 , 6 } V=\{1, 2, 3, 4, 5, 6\} V={1,2,3,4,5,6},边集 E = { ( 1 , 2 ) , ( 1 , 5 ) , ( 2 , 3 ) , ( 2 , 5 ) , ( 3 , 4 ) , ( 4 , 5 ) , ( 4 , 6 ) } E=\{(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)\} E={(1,2),(1,5),(2,3),(2,5),(3,4),(4,5),(4,6)} 。在无向图中,边 ( u , v ) (u, v) (u,v)和边 ( v , u ) (v, u) (v,u)是一样的,因此只要记录一个就行了。简而言之,对称。
    图1-2:有向图
    图1-2:有向图 2
    有向图也很好理解,就是加上了方向性,顶点 ( u , v ) (u, v) (u,v)之间的关系和顶点 ( v , u ) (v,u) (v,u)之间的关系不同,后者或许不存在。例如,地图应用中必须存储单行道的信息,避免给出错误的方向。

    加权图:与加权图对应的就是无权图,如果觉得不好听,那就叫等权图。如果一张图不含权重信息,我们就认为边与边之间没有差别。不过,具体建模的时候,很多时候都需要有权重,比如对中国重要城市间道路联系的建模,总不能认为从北京去上海和从北京去广州一样远(等权)。

    还有很多细化的概念,有兴趣的自己了解咯。我觉得就没必要单独拎出来写,比如:无向图中,任意两个顶点间都有边,称为无向完全图;加权图起一个新名字,叫网(network)……然而,如无必要,毋增实体。

    两个重要关系:

    • 邻接(adjacency):邻接是两个顶点之间的一种关系。如果图包含 ( u , v ) (u,v) (u,v),则称顶点 v v v与顶点 u u u邻接。当然,在无向图中,这也意味着顶点 u u u与顶点 v v v邻接。
    • 关联(incidence):关联是边和顶点之间的关系。在有向图中,边 ( u , v ) (u,v) (u,v)从顶点 u u u开始关联到 v v v,或者相反,从 v v v关联到 u u u。注意,有向图中,边不一定是对称的,有去无回是完全有可能的。

    细化关联这个概念,就有了顶点的入度(in-degree)出度(out-degree)。无向图中,顶点的度就是与顶点相关联的边的数目,没有入度和出度。在有向图中,我们以图1-2为例,顶点10有2个入度, 3 → 10 3\rightarrow10 310 11 → 10 11\rightarrow10 1110,但是没有从10指向其它顶点的边,因此顶点10的出度为0。

    路径(path):依次遍历顶点序列之间的边所形成的轨迹。注意,依次就意味着有序,先1后2和先2后1不一样。

    简单路径:没有重复顶点的路径称为简单路径。说白了,这一趟路里没有出现绕了一圈回到同一点的情况,也就是没有
    图1-3:四顶点的有向带环图
    图1-3:四顶点的有向带环图3

    :包含相同的顶点两次或者两次以上。图1-3中的顶点序列 &lt; 1 , 2 , 4 , 3 , 1 &gt; &lt;1,2,4,3,1&gt; <1,2,4,3,1>,1出现了两次,当然还有其它的环,比如 &lt; 1 , 4 , 3 , 1 &gt; &lt;1,4,3,1&gt; <1,4,3,1>

    无环图:没有环的图,其中,有向无环图有特殊的名称,叫做DAG(Directed Acyline Graph)(最好记住,DAG具有一些很好性质,比如很多动态规划的问题都可以转化成DAG中的最长路径、最短路径或者路径计数的问题)。
    下面这个概念很重要:
    图1-4:两个连通分支
    图1-4:两个连通分支

    连通的:无向图中每一对不同的顶点之间都有路径。如果这个条件在有向图里也成立,那么就是强连通的。图1-4中的图不是连通的,我丝毫没有侮辱你智商的意思,我只是想和你说,这图是我画的,顶点标签有点小,应该看到a和d之间没有通路。

    • 连通分支:不连通的图是由2个或者2个以上的连通分支的并。这些不相交的连通子图称为图的连通分支
      图1-5:有向图的连通分支
      图1-5:有向图的连通分支

    • 有向图的连通分支:将有向图的方向忽略后,任何两个顶点之间总是存在路径,则该有向图是弱连通的有向图的子图是强连通的,且不包含在更大的连通子图中,则可以称为图的强连通分支

    图1-5中, a a a e e e没有到 { b , c , d } \{b,c,d\} {b,c,d}中的顶点的路径,所以各自是独立的连通分支。因此,图1-5中的图有三个强连通分支,用集合写出来就是: { { a } , { e } , { b , c , d } } \{\{a\}, \{e\}, \{b, c, d\}\} {{a},{e},{b,c,d}}(已经用不同颜色标出)。

    图1-6:关节点
    图1-6:关节点

    关节点(割点):某些特定的顶点对于保持图或连通分支的连通性有特殊的重要意义。如果移除某个顶点将使图或者分支失去连通性,则称该顶点为关节点。如图1-6中的c。

    双连通图:不含任何关节点的图。
    关节点的重要性不言而喻。如果你想要破坏互联网,你就应该找到它的关节点。同样,要防范敌人的攻击,首要保护的也应该是关节点。在资源总量有限的前提下,找出关节点并给予特别保障,是提高系统整体稳定性和鲁棒性的基本策略。

    桥(割边):和关节点类似,删除一条边,就产生比原图更多的连通分支的子图,这条边就称为割边或者

    1.2 一些有趣的图概念

    这一部分属于图论的内容,基础图算法不会用到,但是我觉得挺有意思的,小记如下。
    同构4:图看起来结构不一样,但它是一样的。假定有 G 1 G_1 G1 G 2 G_2 G2,那么你只要确认对于 G 1 G_1 G1中的所有的两个相邻点 a a a b b b,可以通过某种方式 f f f映射到 G 2 G_2 G2,映射后的两个点 f ( a ) f(a) f(a) f ( b ) f(b) f(b)也是相邻的。换句话说,当两个简单图同构时,两个图的顶点之间保持相邻关系的一一对应。
    图1-7:图的同构
    图1-7:图的同构

    图1-7就展示了图的同构,这里顶点个数很少判断图的同构很简单。我们可以把v1看成u1,自然我们会把u3看出v3。用数学的语言就是 f ( u 1 ) = v 1 f(u_1)=v_1 f(u1)=v1 f ( u 3 ) = v 3 f(u_3)=v_3 f(u3)=v3。u1的另外一个连接是到u2,v1的另外一个连接是到v4,不难从相邻顶点的关系验证 f ( u 2 ) = v 4 f(u_2)=v_4 f(u2)=v4 f ( u 4 ) = v 2 f(u_4)=v_2 f(u4)=v2

    欧拉回路(Euler Circuit):小学数学课本上的哥尼斯堡七桥问题,能不能从镇里的某个位置出发不重复的经过所有桥(边)并且返回出发点。这也就小学的一笔画问题,欧拉大神解决里这个问题,开创了图论。

    结论很简单:至少2个顶点的连通多重图存在欧拉回路的充要条件是每个顶点的度都是偶数。证明也很容易,大家有兴趣可以阅读相关资料。结论也很好理解,从某个起点出发,最后要回起点,中间无论路过多少次起点,都会再次离开,进、出的数目必然相等,故一定是偶数。

    哈密顿回路(Hamilton Circuit):哈密顿回路条件就比欧拉回路严格一点,不能重复经过点。你可能会感到意外,对于欧拉回路,我们可以轻而易举地回答,但是我们却很难解决哈密顿回路问题,实际上它是一个NP完全问题

    这个术语源自1857年爱尔兰数学家威廉·罗万·哈密顿爵士发明的智力题。哈密顿的智力题用到了木质十二面体(如图1-8(a)所示,十二面体有12个正五边形表面)、十二面体每个顶点上的钉子、以及细线。十二面体的20个顶点用世界上的不同城市标记。智力题要求从一个城市开始,沿十二面体的边旅行,访问其他19个城市,每个恰好一次,最终回到第一个城市。
    图1-8:哈密顿回路问题
    图1-8:哈密顿回路问题
    因为作者不可能向每位读者提供带钉子和细线的木质十二面体,所以考虑了一个等价的问题:对图1-8(b)的图是否具有恰好经过每个顶点一次的回路?它就是对原题的解,因为这个平面图同构于十二面体顶点和边。

    著名的**旅行商问题(TSP)**要求旅行商访问一组城市所应当选取的最短路线。这个问题可以归结为求完全图的哈密顿回路,使这个回路的边的权重和尽可能的小。同样,因为这是个NP完全问题,最直截了当的方法就检查所有可能的哈密顿回路,然后选择权重和最小的。当然这样效率几乎难以忍受,时间复杂度高达 O ( n ! ) O(n!) O(n!)

    在实际应用中,我们使用的启发式搜索等近似算法,可以完全求解城市数量上万的实例,并且甚至能在误差1%范围内估计上百万个城市的问题。

    关于旅行商问题目前的研究进展,可以到http://www.math.uwaterloo.ca/tsp/进一步了解。

    1.3 小结

    以为可以一带而过,结果写了那么多。也没什么好总结的了,当然这些也至是图论概念的一小部分,还有一些图可能我们以后也会见到,比如顺着图到网络流,就会涉及二分图,不过都很好理解,毕竟有图。

    2 图的表示

    2.1 邻接链表与邻接矩阵

    图最常见的表示形式为邻接链表邻接矩阵。邻接链接在表示稀疏图时非常紧凑而成为了通常的选择,相比之下,如果在稀疏图表示时使用邻接矩阵,会浪费很多内存空间,遍历的时候也会增加开销。但是,这不是绝对的。如果图是稠密图,邻接链表的优势就不明显了,那么就可以选择更加方便的邻接矩阵。

    还有,顶点之间有多种关系的时候,也不适合使用矩阵。因为表示的时候,矩阵中的每一个元素都会被当作一个表。

    2.1.1 存储问题

    如果使用邻接矩阵还要注意存储问题。矩阵需要 n 2 n^2 n2个元素的存储空间,声明的又是连续的空间地址。由于计算机内存的限制,存储的顶点数目也是有限的,例如:Java的虚拟机的堆的默认大小是物理内存的1/4,或者1G。以1G计算,那么创建一个二维的int[16384][16384]的邻接矩阵就已经超出内存限制了。含有上百万个顶点的图是很常见的, V 2 V^2 V2的空间是不能满足的。
    因此,偷个懒,如果对邻接矩阵感兴趣,可以自己找点资料。很容易理解的。

    2.1.2 邻接链表的实现

    邻接链表的实现会比邻接矩阵麻烦一点,但是邻接链表的综合能力,包括鲁棒性、拓展性都比邻接矩阵强很多。没办法,只能忍了。
    图1-9:邻接链表示意图
    图1-9:邻接链表示意图

    从图1-9不能看出邻接链表可以用线性表构成。顶点可以保持在数组或者向量(vector)中,邻接关系则用链表实现,利用链表高效的插入和删除,实现内存的充分利用。有利必有弊,邻接矩阵可以高效的判定两个顶点之间是否有邻接关系,邻接链表无疑要遍历一次链表。

    邻接链表的瓶颈在于链表的查找上,如果换成高效的查找结构,就可以进一步地提高性能。例如,把保存顶点邻接关系的链表换成通常以红黑树为基础set。如果一定要名副其实,就要叫成邻接集。类似的,顶点的保存也有“改进”方案。比如,使用vector通常用int表示顶点,也无法高效地进行顶点的插入删除。如果把顶点的保存换成链表,无疑可以高效地进行顶点的插入和删除,但是访问能力又会大打折扣。没错,我们可以使用set或者map来保存顶点信息。

    C++11中引入了以散列表为基础unordered_setunordered_map,就查找和插入而言,统计性能可能会高于红黑树,然而,散列表会带来额外的内存开销,这是值得注意的。

    具体问题,具体分析,图的结构不同,实现图的结构也应该随之不同。大概也是这个原因,像C++、Java、Python等语言,都不提供具体的Graph。举个例子,直接使用vector保存顶点信息,list保存邻接关系,使用的顶点id连续5。那么在添加边 O ( 1 ) O(1) O(1),遍历顶点的邻接关系 O ( V ) O(V) O(V)还有空间消耗 O ( V + E ) O(V+E) O(V+E)上都是最优的。当然,类似频繁删除边,添加边(不允许平行边),删除顶点,添加顶点,那么这种比较简易的结构就不太适合了。

    2.3 量化选择

    我们稍微量化一下稀疏图和稠密图的标准。当我们声称图的是稀疏的,我们近似地认为边的数量 ∣ E ∣ |E| E大致等于顶点的个数 ∣ V ∣ |V| V,在稠密图中,我们可以不难得到 ∣ E ∣ |E| E近似为 ∣ V 2 ∣ |V^2| V2。在此,我们不妨定义均衡图是边的数量为 ∣ V 2 ∣ / log ⁡ ∣ V ∣ |V^2|/\log |V| V2/logV的图。

    图算法中,根据图的结构,经常会有两个算法变种,时间复杂度也不尽相同。可能有一个是 O ( ( V + E ) log ⁡ V ) O((V+E)\log V) O((V+E)logV),另一个是 O ( V 2 + E ) O(V^2+E) O(V2+E)。选择哪个算法更为高效取决于图是否是稀疏的。

    图类型 O ( ( V + E ) log ⁡ V ) O((V+E)\log V) O((V+E)logV)比较关系 O ( V 2 + E ) O(V^2+E) O(V2+E)
    稀疏图: E E E O ( V ) O(V) O(V) O ( V log ⁡ V ) O(V\log V) O(VlogV)< O ( V 2 ) O(V^2) O(V2)
    均衡图: E E E O ( V 2 / log ⁡ V ) O(V^2/\log V) O(V2/logV) O ( V 2 + V log ⁡ V ) = O ( V 2 ) O(V^2+V\log V)=O(V^2) O(V2+VlogV)=O(V2)= O ( V 2 + V 2 / log ⁡ V ) = O ( V 2 ) O(V^2+V^2/\log V)=O(V^2) O(V2+V2/logV)=O(V2)
    稠密图: E E E O ( V 2 ) O(V^2) O(V2) O ( V 2 log ⁡ V ) O(V^2\log V) O(V2logV)> O ( V 2 ) O(V^2) O(V2)

    3 图的实现

    3.1 代码约定

    因为用Markdown,所以我怕有时候排版的时候空格出现问题,4空格调整太麻烦,加上可能4空格有时候不是特别紧凑,所以代码全部是2空格缩进。另外,我就不打算像教科书一样写那种一本正经的代码,拆成头文件加源文件。还有很多偷懒和不负责的地方,不过,换来了性能。还有,auto还是挺好用的,因此代码会用到少量C++11。

    3.2 想想需要什么功能

    3.2.1 图的数据结构

    就学习算法的目的而言,频繁添加和删除顶点是不需要的,因此代码实现时,为方便起见顶点仍然使用vector保存,边的话进阶点,使用set,这样就防止出现平行边了。还有,我比较放心自己,很多方法不加检查。还是那句话,具体问题,具体分析,具体实现。

    3.2.2 图的操作

    既然选择用vector+set,我们来考虑一下基本操作,至于那些后来算法用到的,后面再补充实现。

    数据成员:

    • 边的数量
    • 顶点的数量
    • vectorset构成的图结构

    功能:

    • 添加边
    • 删除边
    • 添加顶点
    • 删除顶点
    • 判断是否有邻接关系
    • 返回顶点的邻接集:不推荐直接使用这个,建议用迭代器
    • 迭代器begincbegin
    • 迭代器endcend

    其它

    • 构造:初始化n个顶点
    • 构造:从字符串读取文件中的图信息,便于加载图信息
    • 析构函数:都是使用STL和动态变量,不用我们操心
    • 数据成员的取值方法
    • 辅助方法:打印图

    3.3.3 声明与内联实现

    #include <iostream>
    #include <vector>
    #include <set>
    #include <list>
    #include <fstream>
    #include <limits>
    #include <queue>
    
    // 邻接集合
    typedef std::set<int> AdjSet;
    // 邻接集
    class Graph {
     protected:
      // 邻接表向量
      std::vector<AdjSet> vertices_;
      // 顶点数量
      int vcount_;
      // 边的数量
      int ecount_;
      bool directed_;
     public:
      Graph(bool directed = false)
        : ecount_(0), vcount_(0),
          vertices_(0), directed_(directed) {};
      Graph(int n, bool directed)
        : ecount_(0), vcount_(n),
          vertices_(n), directed_(directed) {};
      // 从文件中初始化
      Graph(const char *filename, bool directed);
      virtual ~Graph() {
        vertices_.clear();
        vcount_ = 0;
        ecount_ = 0;
      }
      // 取值函数
      virtual int vcount() const { return vcount_; };
      virtual int ecount() const { return ecount_; };
      virtual bool directed() const { return directed_; };
      // 某条边是否存在
      virtual bool IsAdjacent(const int &u, const int &v);
      // 约定:成功返回 0,不存在 -1,已存在 1
      // 添加边
      virtual int AddEdge(const int &u, const int &v);
      // 添加顶点
      virtual int AddVertex();
      // 删除边
      virtual int RemoveEdge(const int &u, const int &v);
      // 删除顶点
      virtual int RemoveVertex(const int &u);
      // 返回顶点的邻接集
      virtual std::set<int>& Adj(const int &u) { return vertices_[u]; }
      // 迭代器
      virtual AdjSet::const_iterator begin(const int u) { return vertices_[u].begin(); };
      virtual AdjSet::const_iterator end(const int u) { return vertices_[u].end(); };
      virtual AdjSet::const_iterator cbegin(const int u) const { return vertices_[u].cbegin(); };
      virtual AdjSet::const_iterator cend(const int u) const { return vertices_[u].cend(); };
    }; // class Graph
    

    3.3 开工

    因为图结构实现还是比较简单的,代码都很短。

    3.3.1 从文件中构造图

    文件格式,先顶点数量、边数量,然后顶点对表示边。缺省bool值默认无向
    例如

    6
    8
    0 1
    0 2
    0 5
    2 3
    2 4
    2 1
    3 5
    3 4
    

    代码实现:

    Graph::Graph(const char *filename, bool directed = false) {
      directed_ = directed;
      int a, b;
      // 默认能打开,如果想安全,使用if (!infile.is_open())作进一步处理
      std::ifstream infile(filename, std::ios_base::in);
      // 节点和边数量
      infile >> a >> b;
      vcount_ = a;
      ecount_ = b;
      vertices_.resize(vcount_);
      // 读取边
      for (int i = 0; i < ecount_; ++i) {
        infile >> a >> b;
        int v = a;
        int w = b;
        vertices_[v].insert(w);
        if (!directed_) {
          vertices_[w].insert(v);
        }
      }
      infile.close();
    }
    

    3.3.2 添加和删除顶点

    // 添加顶点
    int Graph::AddVertex() {
      std::set<int> temp;
      vertices_.push_back(temp);
      ++vcount_;
      return 0;
    }
    
    // 删除顶点
    int Graph::RemoveVertex(const int &u) {
      if (u > vertices_.size()) {
        return -1;
      }
      // 遍历图,寻找与顶点的相关的边
      // 无向图,有关的边一定在该顶点的邻接关系中
      if (!directed_) {
        int e = vertices_[u].size();
        vertices_.erase(vertices_.begin() + u);
        ecount_ -= e;
        --vcount_;
        return 0;
      } else {
        // 遍历图
        for (int i = 0; i < vertices_.size(); ++i) {
          RemoveEdge(i, u);
        }
        vertices_.erase(vertices_.begin() + u);
        --vcount_;
        return 0;
      }
      return -1;
    }
    

    3.3.3 添加和删除边

    // 添加边
    int Graph::AddEdge(const int &u, const int &v) {
      // 不绑安全带,使用需谨慎
      vertices_[u].insert(v);
      if (!directed_) {
        vertices_[v].insert(u);
      }
      ++ecount_;
      return 0;
    }
    
    // 删除边
    int Graph::RemoveEdge(const int &u, const int &v) {
      auto it_find = vertices_[u].find(v);
      if (it_find != vertices_[u].end()) {
        vertices_[u].erase(v);
        --ecount_;
      } else {
        return -1;
      }
      if (directed_) { return 0; }
      // 无向图删除反向边
      it_find = vertices_[v].find(u);
      if (it_find != vertices_[u].end()) {
        vertices_[v].erase(u);
      } else {
        // 人和人之间的信任呢?
        return -1;
      }
      return 0;
    }
    

    3.3.4 是否有邻接关系

    // 检查两个顶点之间是否有邻接关系
    bool Graph::IsAdjacent(const int &u, const int &v) {
      if (vertices_[u].count(v) == 1) {
        return true;
      }
      return false;
    }
    

    3.3.5 其它:打印图

    这个用到了cout,又考虑到非功能性方法,不建议放在类中。

    // 打印图
    void PrintGraph(const Graph &graph) {
      for (int i = 0; i < graph.vcount(); i++) {
        std::cout << i << " -->";
        for (auto it = graph.cbegin(i); it != graph.cend(i); ++it) {
          std::cout << " " << *it;
        }
        std::cout << std::endl;
      }
    }
    

    3.5 小结

    图是相当灵活的,我想这也是为什么STL库不提供Graph的原因。我们可以发现,利用STL的基础设施,我们可以很快的搭建Graph。至于选择什么基础设施,没有标准答案。对于不同的问题会有不同的最佳答案。我们只是演示,不对特定问题进行进行建模,可以不管什么性能,也没打算泛化(不造库,谢谢),不过分考虑实现和图操作分离问题。嗯,就这样咯,还是赶紧进入更加激动人心的图算法吧。

    后记

    我水平有限,错误难免,还望各位加以指正。

    参考资料

    1. Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest,等. 算法导论(原书第3版).
    2. Robert Sedgewick, Kevin Wayne. 算法(原书第4版).
    3. 邓俊辉. 数据结构(C++语言版)(第3版).
    4. Kenneth H.Rosen. Discrete Mathematics and Its Applications(Seventh Edition).
    5. 维基百科相关词条

    1. https://en.wikipedia.org/wiki/Graph_(discrete_mathematics) ↩︎

    2. https://en.wikipedia.org/wiki/Directed_graph ↩︎

    3. https://en.wikipedia.org/wiki/Directed_graph ↩︎

    4. 同构(isomorphism)这个词来自希腊语字根:“isos”表示相等;“morphe”表示形式。 ↩︎

    5. 注意这通常是可以做到的,这意味着我们只关注图的拓扑结构,不关心顶点id的意义。如果你非要在图中保存额外的信息,那么就应该使用树结构或者随机化的hash方案。 ↩︎

    展开全文
  • 线性表、树形结构和图形结构的区别 线性表:数据元素之间仅有线性关系,每个数据元素只有一个直接前驱和一个直接后继 ...图形结构:结点之间的关系可以是任意的,中任意两个数据元素之间都可能相关...

    线性表、树形结构和图形结构的区别

    线性表:数据元素之间仅有线性关系,每个数据元素只有一个直接前驱和一个直接后继

    树形结构:数据元素之间有明显的层次关系,并且每一层上的数据元素可能和下一层中多个元素(即其孩子结点)相关,但只能和上一层中一个元素(即其双亲结点)相关

    图形结构:结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关

    展开全文
  • 关于图结构的相似度比较

    千次阅读 2015-01-15 13:57:05
    搞数据挖掘是个很死脑细胞的活儿,最近研究图结构的相似度比较,过目了不少论文,脑门子都看得有点儿发热了,先做一下总结,免得短路烧了。 图这东西应该算是数据结构里面终极难搞的结构了,单一个同构问题,就已经...
  • 在现实生活中,公司的部门设计会涉及到很多子部门,然后子部门下面又存在子部门,形成类似判断的树状结构,比如说评论楼中楼的评论树状图,职位管理的树状图结构等等,实现类似的树状图数据结构是在开发中经常出现的...
  • 一步一步写算法(之图结构

    万次阅读 多人点赞 2011-10-30 15:33:20
     是数据结构里面的重要一章。通过,我们可以判断两个点之间是不是具有连通性;通过,我们还可以计算两个点之间的最小距离是多少;通过,我们还可以根据不同的要求,寻找不同的合适路径。当然,有的时候为了...
  • Python图结构-树的实现

    千次阅读 2017-06-05 15:45:19
    大部分树算法都可以被理解成一般概念中的思路,但特定的树结构会使得它们更容易实现。 例子: 带根的树结构,这种树的每条边都从根出发,并向下方延伸,此类结构往往代表的是某个数据集所拥有的层次结构,其...
  • tensorflow从.meta文件中导出图结构

    万次阅读 2018-01-30 11:20:32
    但是博主在尝试使用该解决方案直接加载已经持久化的而不必重新定义结构,进行predict时,源代码如下: import input_data mnist = input_data.read_data_sets('MNIST_data', one_hot=True) import tensorflow...
  • 图解的存储结构

    千次阅读 2017-10-19 23:14:26
    所以在刚接触图形结构的时候,对于如何实现图形结构往往感到很困惑,后来发现我们其实只要弄清楚了的存储结构那么用代码实现起来并不困难。要清楚地理解的存储结构,首先要明白的存储结构里要存储些什么东西。...
  • ResNet结构图

    千次阅读 2018-07-04 16:53:28
    ResNet结构图
  • 数据结构--(Java版)

    万次阅读 多人点赞 2018-05-02 16:23:37
    线性表和树两类数据结构,线性表中的元素是“一对一”的关系,树中的元素是“一对多”的关系,本章所述的图结构中的元素则是“多对多”的关系。 图(Graph)是一种复杂的非线性结构,在图结构中,每个元素都可以...
  • java知识结构图

    万次阅读 2017-10-07 17:07:07
    java知识结构图
  • JVM架构内存结构图

    万次阅读 2020-09-14 03:40:54
    在线分享地址:JVM内存结构图
  • 组合结构图

    千次阅读 2017-01-01 23:29:44
    1,组合结构图将每一个类放在一个整体中,从类的内部结构来审视一个类。 2,组合结构图可用于表示一个类的内部结构。 二:主要组成元素  >部件(Part):表示被描述事物所拥有的内部成分。  >连接件...
  • 系统功能结构图

    万次阅读 2013-07-06 18:56:02
    1、系统前台功能结构图 2、系统后台功能结构图
  • C/C++实现数据结构的遍历算法

    万次阅读 2018-10-08 09:38:37
    有向和无向这里就先假设为邻接矩阵表示,直观的体现下的存储结构的特点。邻接表不过就是有入边和出边来体现的点集和边集的特点。这两种逻辑结构其实并没有太大的区别。 就像树有三种遍历方式一样(前序遍历...
  • 0701 图结构导学 0702 图的定义 0703 图的基本术语 0704 图的邻接矩阵存储结构及算法 0705 图的邻接表存储结构及算法 0706 图的遍历 0707 非连通图的遍历 0708 DFS的应用 0709 BFS的应用【项目1 - 图基本算...
  • 【数据结构(Graph)

    千次阅读 2017-06-14 10:44:47
    简单对比:(graph):是一种较线性表和树更为复杂的数据结构,图形结构中,结点之间的关系可以是任意的,中任意两个数据元素之间都可能相关 线性表:数据元素之间仅有线性关系,每个数据元素只有一个直接前驱...
  • 图是不同于树的另一种非...在图结构中,数据元素之间的关系则是多对多的关系。即图中的每个数据元素可以和图中任意别的数据元素相关,所以图是一种比树更复杂的数据结构。 树结构可以看做是图的一种特例。   图...
  • 主要是因为Tensorboard中查看到的图结构太混乱了,包含了网络中所有的计算节点(读取数据节点、网络节点、loss计算节点等等)。更可怕的是,如果一个计算节点是由多个基础计算(如加减乘除等)构成,那么在...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,766,333
精华内容 1,106,533
关键字:

图结构