共计 7213 个字符，预计需要花费 19 分钟才能阅读完成。
图 github 直达地址 https://github.com/fanshyiis/…
在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。
注意：顶点有时也称为节点或者交点，边有时也称为链接。
一个图可以表示一个社交网络，每一个人就是一个顶点，互相认识的人之间通过边联系。
理论上，图就是一堆顶点和边对象而已，但是怎么在代码中来描述呢？有两种主要的方法：邻接列表和邻接矩阵。
邻接列表：在邻接列表实现中，每一个顶点会存储一个从它这里开始的边的列表。比如，如果顶点 A 有一条边到 B、C 和 D，那么 A 的列表中会有 3 条边
邻接列表只描述了指向外部的边。A 有一条边到 B，但是 B 没有边到 A，所以 A 没有出现在 B 的邻接列表中。查找两个顶点之间的边或者权重会比较费时，因为遍历邻接列表直到找到为止。
邻接矩阵：在邻接矩阵实现中，由行和列都表示顶点，由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连、如果相连这个值表示的是相连边的权重。例如，如果从顶点 A 到顶点 B 有一条权重为 5.6 的边，那么矩阵中第 A 行第 B 列的位置的元素值应该是 5.6：
往这个图中添加顶点的成本非常昂贵，因为新的矩阵结果必须重新按照新的行 / 列创建，然后将已有的数据复制到新的矩阵中。所以使用哪一个呢？大多数时候，选择邻接列表是正确的。下面是两种实现方法更详细的比较。假设 V 表示图中顶点的个数，E 表示边的个数。
“检查相邻性”是指对于给定的顶点，尝试确定它是否是另一个顶点的邻居。在邻接列表中检查相邻性的时间复杂度是 O(V)，因为最坏的情况是一个顶点与每一个顶点都相连。在 稀疏图的情况下，每一个顶点都只会和少数几个顶点相连，这种情况下相邻列表是最佳选择。如果这个图比较密集，每一个顶点都和大多数其他顶点相连，那么相邻矩阵更合适。
了解了图的基本定义后我们来看下如何用 es6 的类 class 思想来实现图类
首先我们先定义两个辅助类
class Dictionary {
constructor () {
this.items = {}
}
has (key) {
return key in this.items
}
set (key, val) {
this.items[key] = val
}
delete (key) {
if (this.has(key)) {
delete this.items[key]
return true
} else {
return false
}
}
get (key) {
return this.has(key)? this.items[key] : undefined
}
values () {
let values = []
for (let k in this.items) {
if (this.has(k)) {
values.push(this.items[k])
}
}
return values
}
}
class Queue {
constructor () {
this.items = []
}
enqueue (element) {
this.items.push(element)
}
dequeue () {
return this.items.shift()
}
isEmpty() {
return this.items.length === 0
}
}
Dictionary 字典类来辅助存贮键值对 Queue 队列类来存贮队列
// 定义 class Graph
class Graph {
constructor () {
this.vertices = []
this.adjList = new Dictionary()
}
}
定义 Graph 类并且在构造函数里初始化字段 vertices 存储点信息 adjList 存储顶点间的链接关系
addVertex (v) {
this.vertices.push(v)
this.adjList.set(v, [])
}
addEdge (v, w) {
this.adjList.get(v).push(w)
}
addVertex 添加顶点的方法，存贮在数组 vertices，并且初始化 adjList 字典里的值 addEdge 添加单向边 接收两个值 在邻接字典里加上从第一个顶点到第二个的关系
到这 一个基本的类就完成了，我们可以通过测试代码来测试
et graph = new Graph()
let mv = [‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’, ‘H’, ‘I’]
mv.map(val => {
graph.addVertex(val)
})
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’)
得到的图
下面我们来定义一个功能来打印图
toString () {
let s = ”
for (let i = 0; i < this.vertices.length; i++) {
s += this.vertices[i] + ‘->’
let neighbors = this.adjList.get(this.vertices[i])
for (let j = 0; j < neighbors.length; j++) {
s += neighbors[j] + ‘ ‘
}
s += ‘\n’
}
return s
}
执行文件 node graph.js
得到结果
A->B C D
B->E F
C->D G
D->G H
E->I
F->
G->
好到这就基本完成类的结构了，下面进行图的遍历
广度优先 – 数据结构 队列
先上代码
BFS (v, callback) {
let color = this.initializeColor(),
queue = new Queue()
queue.enqueue(v)
while (!queue.isEmpty()) {
let u = queue.dequeue(),
neighbors = this.adjList.get(u)
color[u] = ‘grey’
neighbors.map(val => {
if (color[val] === ‘white’) {
color[val] = ‘grey’
queue.enqueue(val)
}
})
color[u] = ‘black’
if (callback) {
callback(u)
}
}
}
基本思想如下 1. 初始化各个顶点的颜色（白色 – 未访问；灰色 – 已发现；黑色 – 已经探索完）2. 初始化一个队列 3. 首先队列入顶点 v4. 如果队列不会空，则取队列第一个进行探索 5. 探索过程中获取当前顶点的所有邻接顶点，并推进队列 6. 完成 5 后，标记当前为黑色
图示例 A 探索 队列入 B – C – D 完成 A 探索出 B 探索 B 队列再入 E – F 当前 CDEF 完成 B 探索出 C 探索 队列再入 G 当前 DEFG。。。
直到所有顶点探索完
深度优先 – 数据结构 栈
先上代码
DFS (callback) {
let color = this.initializeColor()
this.vertices.map(val => {
if (color[val] === ‘white’) {
this.dfsVisit(val, color, callback)
}
})
}
dfsVisit (u, color, callback) {
color[u] = ‘grey’
if (callback) {
callback(u)
}
let neighbors = this.adjList.get(u)
neighbors.map(val => {
if (color[val] === ‘white’) {
this.dfsVisit(val, color, callback)
}
})
color[u] = ‘black’
}
深度优先的原则以栈为数据结构
基本思想如下 1. 初始化各个顶点的颜色（白色 – 未访问；灰色 – 已发现；黑色 – 已经探索完）2. 对顶点进行遍历并进行 dfsVisit 函数探索 3. 优先进行最新探索的边进行深度探索，完成后标记探索完成
基本步骤如下探索 A 发现 BCD 探索 B 发现 EF 探索 E 发现 I 探索 I，完毕 标记 I 为以探索回到上个分支遍历接着执行探索 F 完成标记 F 为以探索。。。直到返回到顶点 A
完成探索
具体还有 PLus 版的深度和广度优先的算法，具体代码奉上
/*
* @Author: koala_cpx
* @Date: 2019-01-24 10:48:01
* @Last Modified by: koala_cpx
* @Last Modified time: 2019-01-24 10:56:33
*/
class Dictionary {
constructor () {
this.items = {}
}
has (key) {
return key in this.items
}
set (key, val) {
this.items[key] = val
}
delete (key) {
if (this.has(key)) {
delete this.items[key]
return true
} else {
return false
}
}
get (key) {
return this.has(key)? this.items[key] : undefined
}
values () {
let values = []
for (let k in this.items) {
if (this.has(k)) {
values.push(this.items[k])
}
}
return values
}
}
class Queue {
constructor () {
this.items = []
}
enqueue (element) {
this.items.push(element)
}
dequeue () {
return this.items.shift()
}
isEmpty() {
return this.items.length === 0
}
}
class Graph {
constructor () {
this.vertices = []
this.adjList = new Dictionary()
this.time = 0
}
addVertex (v) {
this.vertices.push(v)
this.adjList.set(v, [])
}
addEdge (v, w) {
this.adjList.get(v).push(w)
// this.adjList.get(w).push(v)
}
BFS (v, callback) {
let color = this.initializeColor(),
queue = new Queue()
queue.enqueue(v)
while (!queue.isEmpty()) {
let u = queue.dequeue(),
neighbors = this.adjList.get(u)
color[u] = ‘grey’
neighbors.map(val => {
if (color[val] === ‘white’) {
color[val] = ‘grey’
queue.enqueue(val)
}
})
color[u] = ‘black’
if (callback) {
callback(u)
}
}
}
BFSPlus (v) {
let color = this.initializeColor(),
queue = new Queue(),
d = [],
pred = []
queue.enqueue(v)
this.vertices.map(val => {
d[val] = 0
pred[val] = null
})
while (!queue.isEmpty()) {
let u = queue.dequeue(),
neighbors = this.adjList.get(u)
color[u] = ‘grey’
neighbors.map(val => {
if (color[val] === ‘white’) {
color[val] = ‘grey’
d[val] = d[u] + 1
pred[val] = u
queue.enqueue(val)
}
})
color[u] = ‘black’
}
return {
distances: d,
predecessors: pred
}
}
DFS (callback) {
let color = this.initializeColor()
this.vertices.map(val => {
if (color[val] === ‘white’) {
this.dfsVisit(val, color, callback)
}
})
}
DFSPlus () {
let color = this.initializeColor(),
d = [],
f = [],
p = []
this.time = 0
this.vertices.map(val => {
f[val] = 0
d[val] = 0
p[val] = null
})
this.vertices.map(val => {
if (color[val] === ‘white’) {
this.dfsPlusVisit(val, color, d, f, p)
}
})
return {
discovery: d,
finished: f,
predecessors: p
}
}
dfsPlusVisit (u, color, d, f, p) {
console.log(‘discovery’ + u)
color[u] = ‘grey’
d[u] = ++this.time
let neighbors = this.adjList.get(u)
neighbors.map(val => {
if (color[val] === ‘white’) {
p[val] = u
this.dfsPlusVisit(val, color, d, f, p)
}
})
color[u] = ‘black’
f[u] = ++this.time
console.log(‘explored’ + u)
}
dfsVisit (u, color, callback) {
color[u] = ‘grey’
if (callback) {
callback(u)
}
let neighbors = this.adjList.get(u)
neighbors.map(val => {
if (color[val] === ‘white’) {
this.dfsVisit(val, color, callback)
}
})
color[u] = ‘black’
}
outPut(obj) {
let fromVertex = this.vertices[0],
{predecessors} = obj
this.vertices.map(val => {
let path = new Array()
for (var v = val; v !== fromVertex; v = predecessors[v]) {
path.push(v)
}
path.push(fromVertex)
let s = path.pop()
while (path.length !== 0) {
s += ‘ — ‘ + path.pop()
}
console.log(s)
})
}
initializeColor () {
let color = []
this.vertices.map(val => {
color[val] = ‘white’
})
return color
}
toString () {
let s = ”
for (let i = 0; i < this.vertices.length; i++) {
s += this.vertices[i] + ‘->’
let neighbors = this.adjList.get(this.vertices[i])
for (let j = 0; j < neighbors.length; j++) {
s += neighbors[j] + ‘ ‘
}
s += ‘\n’
}
return s
}
}
let a = new Dictionary()
a.set(‘ss’, 1111)
a.set(‘s1’, 1111)
a.set(‘s2’, 1112)
a.set(‘s3’, 1114)
a.delete(‘s2’)
console.log(a.has(‘s3’))
console.log(a.values())
let graph = new Graph()
let mv = [‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’, ‘H’, ‘I’]
mv.map(val => {
graph.addVertex(val)
})
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’)
console.log(graph.toString())
function print(val) {
console.log(‘vis’ + val)
}
graph.BFS(‘A’, print)
console.log(graph.BFSPlus(“A”))
graph.outPut(graph.BFSPlus(“A”))
graph.DFS(print)
console.log(graph.DFSPlus())
let graph2 = new Graph()
let mv2 = [‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’]
mv2.map(val => {
graph2.addVertex(val)
})
graph2.addEdge(‘A’, ‘C’)
graph2.addEdge(‘A’, ‘D’)
graph2.addEdge(‘B’, ‘D’)
graph2.addEdge(‘B’, ‘E’)
graph2.addEdge(‘C’, ‘F’)
graph2.addEdge(‘F’, ‘E’)
let r = graph2.DFSPlus()
console.log(r)
github 直达地址 https://github.com/fanshyiis/…