本文转载自微信公众号「JS逐日一题」,作家灰灰 。转载本文请洽商JS逐日一题公众号。
一、是什么在计较机科学中,图是一种空洞的数据类型,在图中的数据元素时时称为结点,V是扫数极点的聚积,E是扫数边的聚积
淌若两个极点v,w,只可由v向w,而不行由w向v,那么咱们就把这种情况叫作念一个从 v 到 w 的有向边。v也被称作念运行点,w也被称为绝顶。这种图就被称作念有向图
淌若v和w是莫得法例的,从v到达w和从w到达v是彻底换取的,这种图就被称为无向图
图的结构比拟复杂,任性两个极点之间王人可能存在洽商,因此无法以数据元素在存储区中的物理位置来暗示元素之间的关系
常见抒发图的样式有如下:
连接矩阵 连接表 连接矩阵通过使用一个二维数组G[N][N]进行暗示N个点到N-1编号,通过连接矩阵不错坐窝看出南北极点之间是否存在一条边,只需要检查连接矩阵行i和列j是否吵嘴零值,对于无向图,连接矩阵是对称的
连接表存储样式如下图所示:
在javascript中,不错使用Object进行暗示,如下:
const kaiyungraph = { A: [2, 3, 5], B: [2], C: [0, 1, 3], D: [0, 2], E: [6], F: [0, 6], G: [4, 5] }
图的数据结构还可能包含和每条边关系联的数值(edge value),举例一个标号或一个数值(即权重,weight;暗示破钞、容量、长度等)
二、操作对于图的操作常见的有:
深度优先遍历 广度优先遍历最初构建一个图的连接矩阵暗示,如底下的图:
用代码暗示则如下:
const graph = { 0: [1, 4], 1: [2, 4], 2: [2, 3], 3: [], 4: [3], }
深度优先遍历
也等于尽可能的往深处的搜索图的分支
已矣想路是,最初应该详情一个根节点,然后对根节点的没拜访过的相邻节点进行深度优先遍历
详情以 0 为根节点,然后进行深度遍历,然后遍历1,接着遍历 2,然后3,此时完成一条分支0 - 1- 2- 3的遍历,换一条分支,也等于4,4后头因为3依然遍历过了,是以就不拜访了
用代码暗示则如下:
const visited = new Set() const dfs = (n) => { console.log(n) visited.add(n) // 拜访过添加纪录 graph[n].forEach(c => { if(!visited.has(c)){ // 判断是否拜访呢过 dfs(c) } }) }
广度优先遍历
先拜访离根节点最近的节点,然后进行入队操作,处罚想路如下:
新建一个部队,把根节点入队 把队头出队并拜访 把队头的没拜访过的相邻节点入队 重迭二、三时代,知说念部队为空用代码标志则如下:
const visited = new Set() const dfs = (n) => { visited.add(n) const q = [n] while(q.length){ const n = q.shift() console.log(n) graph[n].forEach(c => { if(!visited.has(c)){ q.push(c) visited.add(c) } }) } }三、回来
通过上头的初步了解,不错看到图等于由极点的有穷非空聚积和极点之间的边构成的聚积,分红了无向图与有向图
图的抒发形势不错分红连接矩阵和连接表两种形势,在javascript中,则不错通过二维数组和对象的形势进行抒发
图本体是很复杂的,后续还不错延长出无向图和带权图,对应如下图所示:
参考文件
https://zh.wikipedia.org/wiki/图_(数据结构)
https://www.kancloud.cn/imnotdown1019/java_core_full/2159607