日志

前端小白的数据结构学习总结——图

 来源    2020-09-16    0  

什么是图

图是一种非线性的数据结构,是对网的一种抽象的理解,比如说中国铁路网:

图片中可以看到,每个城市之间的由铁路连成了网,这个网中城市则为“点”,铁路则为“线”,那么我们这个“网”再抽象一点,就成了这样的一个图:

通常我们用G=(V, E)来表示图

一些概念

  • vertex:上图中的圆表示一个城市,在图的概念中我们称其为“vertex(顶点)”
  • edge:与顶点相连的表示的是城市之间的铁路,在图的概念中我们称其为“Edge(边)”
  • weight(权):北京到上海铁路1400多公里,那么这个1400就是这边的weight(权),通常这种带有权的图,我们把他称之为,比如中国铁路网,就是一个带权的图
  • degree(度):一座城市链接的铁路的数目,也就是与顶点相连接的边的数目我们称其为“degree(度),在有向图中,因为边存在方向,所以度还分为入度(ID)出度(OD)

无向图和有向图

上文中提到了Edge(边),这个边可以是具备方向的,那么有向图就很好理解了,边具备方向,像这样:

上图中顶点之间的有用箭头来表示方向,这种边我们成为“弧(arc)”用<A, B>表示,而弧呢又分为弧头弧尾,A -> B这样的一个弧中,我们将顶点A成为弧尾将顶点B成为弧头,通常用尖括号表示弧。
与之相反,无向图就是边没有方向的图,用小括号来表示一个边(A,B)

图的表示方式

我们可以用多种形式来标识一个图,有哪些顶点,以及顶点之间的链接关系

邻接矩阵

以矩阵的方式来描述一张图,横竖都是顶点,如果两顶点连接,那么这个位置的值为1,如果不连接则值为0

开发时,我们可以定义一个二维数组,那么这个数组应该是这样的

let array = [
//   A  B  C  D  E  F  G  H  I
    [0, 1, 1, 1, 0, 0, 0, 0, 0],// A
    [1, 0, 0, 0, 1, 1, 0, 0, 0],// B
    [1, 0, 0, 1, 0, 0, 1, 0, 0],// C
    [1, 0, 1, 0, 0, 0, 1, 1, 0],// D
    [0, 1, 0, 0, 0, 0, 0, 0, 1],// E
    [0, 1, 0, 0, 0, 0, 0, 0, 0],// F
    [0, 0, 1, 1, 0, 0, 0, 0, 0],// G
    [0, 0, 0, 1, 0, 0, 0, 0, 0],// H
    [0, 0, 0, 0, 1, 0, 0, 0, 0] // I
]

这里我们就用二维数组描述了一个图,但是上面我们有提到权的概念,如果是有权的图,那么这里二维数组中的值就应该是个权的值,但是这样一想,如果数值标识权的话,没有联通的顶点还弄用0表示吗?其实加权图的邻接矩阵中用无穷表示未连接,应该是这样:

邻接矩阵会存在一个问题,当这个图为稀疏图,即边相对于顶点很少的时候,可能会出现矩阵中大部分都是0,只有极少数为1,但是内存中还是会分配一个这么大的内存空间,这就造成了内存的浪费

邻接表

邻接表则是通过数组或者链表或者Map来描述一个图的链接关系

上图中用表来描述了一个图,以Map为例,key则为顶点,而value则为与顶点相连接的顶点集合,js中可能是这样的

let map = {
    "A" : ["B", "C", "D"],
    "B" : ["A", "E", "F"],
    "C" : ["A", "D", "G"]
    // ... 
}

但是如果说边是带权的,那邻接表应该如何来描述呢?首先value这里如果是顶点的集合,那就是不行的,不能清楚的描述,所以value应该是边的集合

let map = {
    "A" : [
        {
            vertex : "B",
            weight : 100
        },
        {
            vertex : "C",
            weight : 1
        }
    ]
    // ...
}

实现一个Graph类

首先构造函数中初始化一个map,用来存放顶点以及边的数据,我们以一个有向的无权图为例

class Graph{
    constructor(){
         this.vertexMap = new Map();   
    }
}

这个这个图可以添加顶点,将顶点传入,先判断是否重复传入,如果图中已经存在则不再添加

class Graph{
    constructor(){
         this.vertexMap = new Map();   
    }
    
    addVertex(vertex){
        // 先判断顶点是否已经添加,如果已经添加则不再添加
        if(!this.vertexMap.has(vertex)){
            this.vertexMap.set(vertex, []);
        }
    }
    
    // 同时,定义一个获取所有顶点的方法
    getVertexes(){
        return this.vertexMap.keys();
    }
}

添加完了顶点我们还能添加边,要描述边,那么自然需要两个顶点来描述,所以这个方法传入两个参数,第一个参数为弧尾,第二个参数为弧头

class Graph{
    constructor(){
         this.vertexMap = new Map();   
    }
    
    addEdge(vertex1, vertex2){
        // 先判断弧头是否经存在,不存在的话先保存弧头
        if(!this.vertexMap.has(vertex1)){
            this.vertexMap.set(vertex1, [vertex2]);
        }else{
            this.vertexMap.get(vertex1).push(vertex2);
        }
    }
}

基本的方法实现完了,实现一个打印方法看一看

class Graph{
    constructor(){
         this.vertexMap = new Map();   
    }
    
    print(){
        for(let item of this.vertexMap){
            console.log(item[0] + "-->", item[1]);
        }
    }
}

let g = new Graph();
let vertex = ["A", "B", "C", "D", "E", "F", "G", "H", "I"];

g.addEdge("A", "B");
g.addEdge("A", "C");
g.addEdge("A", "D");
g.addEdge("B", "E");
g.addEdge("B", "F");
g.addEdge("C", "D");
g.addEdge("C", "G");
g.addEdge("D", "G");
g.addEdge("D", "H");

g.print();

最终执行以下能看到结果

A--> [ 'B', 'C', 'D' ]
B--> [ 'E', 'F' ]
C--> [ 'D', 'G' ]
D--> [ 'C', 'G', 'H' ]
E--> [ 'I' ]

图的遍历

我们图中任意一个顶点都可以作为遍历的起点,遍历的就意味着要确保每一个顶点都被访问到,其实遍历的思路非常简单,首先获取到起始点,然后根据起始点的边找到其连接的顶点,然后这样一直循环下去,但是这里就会出现两种情况深度优先遍历广度优先遍历

广度优先搜索

BFS(Breadth Frist Search),顾名思义先大范围搜索,比如说对于这个图

假如我们以顶点A为起点,那么广度优先搜索的顺序就应该是A-B-C-D-E-.....

那么我们的遍历逻辑应该是

  1. 选取一点为起始点
  2. 找到该点的邻接点
  3. 遍历邻接点找到各自的邻接点
  4. 一直循环知道所有的点都访问到

深度优先搜索

DFS(Depth First Search),很好理解,先顺着一条路径一直访问顶点,还是一这个图为例

那么顶点的访问顺序应该是A-B-E-I-F-C-G-D-H

那么我们的逻辑应该是(有点混乱,后面会详细说)

  1. 选取起始点
  2. 获得起始点的第一个邻接点
  3. 循环上个步骤直到这条路径走完访问到最后一个顶点
  4. 向上返回到分支的地方访问另一个邻接点
  5. 继续走完这个路径

两种算法的相同点和不同点

其实对于顶点来说,无非就是三种状态

  1. 没找到
  2. 找到了
  3. 找到了并且获取了所有的邻接点

那么我们在遍历的过程中,需要针对顶点不同的状态做不同的逻辑处理,比如

  1. 遍历的时候发现这个顶点之前已经获取了所有的邻接点,那么就不会再访问了
  2. 上面介绍深度优先搜索的时候中,遍历逻辑步骤4,当我们一条路径走完后,需要往回走找到分支点,那么这个分支点是什么呢?这便是已经找到的但是没有获取邻接点的顶点

其实无论是深度优先还是广度优先,上述的思路都是一致的,但是不同点在哪呢,主要是就在于上文中提到的容器,我们这里放入容器的顺序是

  1. 找到顶点
  2. 按顺序将顶点放入容器
  3. 按顺序取出顶点
  4. 获取取出的顶点的邻接点
  5. 再循环到步骤2

上文提到了按顺序,放进容器按顺序,从容器中拿出按顺序,而这两个算法的不同点就在于顺序不同。

  • 深度优先搜索:将数据储存在(先入后出)中
  • 广度优先搜索:将数据存储在队列(先入先出)中

还是以这个图为例,我们用数组模拟栈和队列:

深度优先搜索,以顶点A为起始点举例

// 定义一个栈,入栈从数组尾部添加,出栈从数组尾部取值
let stack = []

// 首先找到起始点A的邻接点, 并且入栈,A标记为不再访问
stack = [D, C, B]
// 从尾部出栈,把B取出来,获取B的邻接点, B被标记为不再访问
stack = [D, C]  
B - E ,  B - F
// E, F入栈
stack = [D, C, F, E]
// E出栈获取邻接点
stack = [D, C, F]
E - I
// I 入栈
stack = [D, C, F, I]
// I从出栈获取邻接点
stack = [D, C, F]
I - E
// F出栈
// .......

广度优先搜索,同样以顶点A为起始点举例

// 定义一个队列, 添加从数组尾部添加,取出从数组首部取值
let queue = []

// 首先找到起始点A的邻接点,并且加入队列,A标记为不再访问
queue = [B, C, D]
// 从队列首部取出顶点B,获取顶点B的邻接点,B被标记为不再访问
queue = [C, D]
B - E, B - F
// E, F入队列
queue = [C, D, E, F]
// 从首部取出顶点C,获取领接点,C被标记为不再访问
queue = [D, E, F]
C - G, C - D
// D已经存在于队列中,所以只有G入队列
queue = [D, E, F, G]
// 从队列中取出顶点D.....

深度优先搜索代码实现

前面的例子中,我们提到了用代码实现了一个Graph类,并且添加了一些顶点和边,最终打印了结果,接下来,我们接着这个例子,用代码实现一个深度优先搜索,这里就直接贴了,代码注释中有讲解

// 首先定义一个DFS函数,因为是要对图进行深度优先搜索,所以参数接收一个Graph的实例
let DFS = function(graph){
    // 接收到实例后,首先获取图中的顶点
    let vertexes = graph.getVertexes();
    // 定义一个set保存不用再访问的顶点
    let notVisitAgainVertexes = new Set();

     // 定义一个访问节点的方法
    let visit = function(vertex){
        // 先判断当前顶点是不是不用再次访问,是的话这次执行直接跳出
        if(notVisitAgainVertexes.has(vertex)){
            return;
        }
        
        // 将该顶点添加到“不再访问”的容器中
        notVisitAgainVertexes.add(vertex);
        // 获取该顶点的邻接点
        let neighborVertexes = graph.vertexMap.get(vertex);
        
        // 如果存在邻接点,则递归调用visit
        if(neighborVertexes instanceof Array){
            for(let i = 0; i < neighborVertexes.length; i++){
                visit(neighborVertexes[i]);
            }
        }
    }
    
    // 遍历所有顶点,并且执行visit
        for(let vertex of vertexes){
        visit(vertex);
    }
}

上面代码中,我们通过递归调用了visit函数实现了深度优先遍历,我们在visit函数中加一个console.log可以看到结果

按顺序访问顶点 A
按顺序访问顶点 B
按顺序访问顶点 E
按顺序访问顶点 I
按顺序访问顶点 F
按顺序访问顶点 C
按顺序访问顶点 D
按顺序访问顶点 G
按顺序访问顶点 H

是不是和这个图一致

广度优先搜索代码实现

未完待续

数据结构学习之图的遍历(邻接表和邻接矩阵)
日志数据结构学习之图的遍历(邻接表和邻接矩阵) 0x1 问题描述 ​ 建立一个邻接表和邻接矩阵的算法 0x2 代码如下 #include <iostream> #include <str ...
数据结构学习笔记05图(最小生成树 Prim Kruskal)
日志最小生成树Minimum Spanning Tree 一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边. 树: 无回路   |V|个顶 ...
数据结构学习笔记05图 (邻接矩阵 邻接表-->BFS DFS、最短路径)
日志数据结构之图 图(Graph) 包含 一组顶点:通常用V (Vertex) 表示顶点集合 一组边:通常用E (Edge) 表示边的集合 边是顶点对:(v, w) ∈E ,其中v, w ∈ V 有向边& ...
2
C语言数据结构基础学习笔记——图
日志图(G)由顶点集(V)和边集(E)组成,G=(V,E) 常用概念: ①V(G)表示图G中顶点的有限非空集,V永不为空: ②用|V|表示图G中顶点的个数,也称为图G的阶: ③E(G)表示图G中顶点之间关 ...
产品经理学习 – 脑图
问答开启产品经理学习之路,学习之前最先把思维导图学号.::
1
python学习 – 脑图
问答Python 学习, 廖雪峰::
1
Java高级学习 – 脑图
问答java高级语法学习有兴趣的可以加微信 careme900123::
3
如何高效学习 – 脑图
问答关于如何高效学习的思维导图,欢迎交流::
1
高效学习 – 脑图
问答如何高效学习::
1
前端知识体系_总 – 脑图
问答前端知识体系汇总::
1
GIT学习 – 脑图
问答git学习,基于官方文档制作的,基本上常用的命令和知识都有了,xmind直接导入,恐怕有些图片信息丢失了,开发编辑,希望能完善里面的内容.谢谢::
1
用于动态规划的算法和数据结构学习资源
问答我现在正在学习动态编程,虽然我很了解这个理论,但为新问题设计DP算法仍然很困难. 这就是我现在真正想要的 – 一本书或一个网站,它提出了一个可以通过动态编程解决的问题.还有一个解决方案,有一个解释,我 ...
1
史上最全的,web前端零基础系统学习路线图!
日志史上最全的,web前端零基础,系统学习路线图!学好web前端,前途宽广!如今随着“互联网+”上升到国家战略,软件行业与国民经济关系密,几乎绝大多数行业的发展都会促进软件行业的发展.因此,只要国民经济保 ...
1
前端自动化测试工具doh学习总结(二)
日志一.robot简介 robot是dojo框架中用来进行前端自动化测试的工具,doh主要目的在于单元测试,而robot可以用来模仿用户操作来测试UI.总所周知,Selenium也是一款比较流行的前端自动 ...
前端自动化测试工具doh学习总结(一)
日志前言 项目中需要用到前端自动化测试,自己被当作一个探针研究了下目前用的比较多的web自动化测试工具.一开始研究的是的selenium,但由于项目使用了大量的dijit控件,写起testCase来很费劲 ...
1
前端小白的个人习惯和笔记(一)
日志快键键 已经敲代码这么久,分享一下自己的小习惯(可能有点乱有点杂) win+S 可以说是window用户的神器,可以随意开启全局的软件,配合cmd使用,alt+F4直接关闭这样就省下按鼠标的时间 ct ...
1
前端小白的gulp入门
日志gulp新手入门 全局安装 cnpm install -g gulp 本地安装cnpm install gulp -D 如果项目没有package.json,记得npm init 安装插件cnpm i ...
2
数据结构7.4_图的连通性问题
日志=================================================== 一.无向图的连通分量和生成树 在对无向图进行遍历时,对于连通图,仅需从图中任一顶点出发,进行深度 ...
2
数据结构7.3_图的遍历
日志我们希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次. 这一过程就叫做图的遍历. 图的遍历算法是求解图的连通性问题.拓扑排序和求关键路径等算法的基础. 然而,图的遍历要比树的遍历复杂 ...
数据结构7.2_图的存储结构
日志由于图的结构比较复杂,任意两个顶点之间都可能存在联系,因此无法以数据元素在存储区中的物理位置来表示元素之间的关系. 即图没有顺序映像的存储结构. 另一方面,多重链表表示图是一件自然的事.它是一种最简单 ...
1