只有把所学总结，形成理论，形成新的名称，才能被铭记，才能进步。
[h2]图的定义[/h2]常用的数据结构有队列、栈、链表、树、图等。
图是由顶点和边形成的结构；它是一种很灵活的数据结构，但是如果在图中没有顶点的话就不能以图形结构来定义。两个顶点之间的关系我们用边来表示；这种由顶点形成的集合和边形成的集合结合在一起就是图这种数据结构；这是在程序语言中的定义。在程序中每个抽象的东西都可以被量化，也就是数据化。
有方向的边形成的图是有向图，反正则是无向图。
连接一个顶点的边的数量被称为该顶点的度；如果边有方向，那么度也有入度和出度之分。同样顶点也有了不同的定义：起始顶点和结束顶点。
如果在图中每两个顶点之间都存在边，那么这种图是完全图；如果边有方向，且每两个顶点都有出度和入度就是有向完全图，反之就是无向完全图。
如果对边进行量化，我可以称之为权重，也就是边承载的意义，比如时间、距离等等。
如果删除一个顶点会对图结构造成影响，比如形成两个图；那么这个顶点可以称为关节点。同样，如果删除边也同上一样，那么这条边可以称为桥。
在无向图中，如果每个顶点都有边，那么可以称为连通图。
关于图还有两个著名的发现：欧拉回路和哈密顿回路。
欧拉回路是从起点出发经过图中所有的边有且一次后回到原点。
哈密顿回路是从任意一点出发经过图中所有点有且一次后回到原点。
![]()
[h2]图的结构[/h2]常用的图结构有两种邻接矩阵和邻接表；
邻接矩阵是用两个数组来实现的，一个用来存储顶点信息，另一个是一个二维数组，用来存储边。
![]()
let oneArr = ['v0', 'v1', 'v2', 'v3'];
let twoArr = [
[0, 1, 1, 1],
[1, 0, 1, 0],
[1, 1, 0, 1],
[1, 0, 1, 0]
]
邻接表是由表头节点和表节点两部分组成，图中每个顶点均对应一个存储在数组中的表头节点。如果这个表头节点所对应的顶点存在邻接节点，则把邻接节点依次存放于表头节点所指向的单向链表中。
![]()
let oneArr = ['v0', 'v1', 'v2', 'v3'];
let twoArr = [
{
data: 'v0',
firstedge: [oneArr[1], oneArr[2], oneArr[3]]
},
{
data: 'v1',
firstedge: [oneArr[0], oneArr[2]]
},
{
data: 'v2',
firstedge: [oneArr[0], oneArr[1], oneArr[3]]
}, {
data: 'v3',
firstedge: [oneArr[0], oneArr[2]]
}
]
[h2]图的遍历[/h2]这里会提到两个概念：广度优先搜索和深度优先搜索。
广度优先搜索从第一个顶点开始，尝试尽可能靠近它的顶点。本质上，这种搜索在图上是逐层移动的，首先检查最靠近第一个顶点的层，再逐渐向下移动到离起始顶点最远的层。
![]()
深度优先搜索包括从一条路径的起始顶点开始追溯，直到到达最后一个顶点，然后回溯，继续追溯下一条路径，直到到达最后的顶点，如此往复，直到没有路径为止。这不是在搜索特定的路径，而是通过搜索来查看在图中有哪些路径可以选择。
[h2]图的实现[/h2]我们来初始化一个类Graph来实现一对多或多对多的关系，接受两个参数，一个是vertextList（顶点列表），另一个参数表示是否初始化一个完全图（一般情况下不会这么写，这里只是但单纯的实现）；
class Graph {
constructor(vertexList = [], isComplete = true) {
this.vertices = vertexList.length // 顶点数
this.edges = 0 // 边数
this.adj = [] // 邻接数组
this.marked = [] // 存储已访问的节点
this.edgeTo = [] // 保存一个顶点到下一个顶点的所有边
this.vertexList = vertexList // 将各个顶点关联到一个符号
this.isComplete = isComplete //设置成完全图
//为每个顶点初始化一个数组用来存储与他相连的节点
for (let i = 0; i < this.vertices; i++) {
this.adj = []
}
// 初始化所有顶点为未访问过
for (let i = 0; i < this.vertices; i++) {
this.marked = false
}
// 初始化完全图
if (this.isComplete) {
this.complete()
}
}
}
添加isComplete属性，来自动实现每个顶点的连接,达到完全图的效果；
complete() {
this.vertexList.forEach((item, index) => {
this.vertexList.forEach((son, i) => {
this.addEdge(index, i)
})
})
}
添加一条边(两个顶点之间的距离），通常情况下，我们会用此方法来实现边，来建立关系。
addEdge(v, w) {
if (v == 0 || w == 0 || v || w) {
if (v == w) return false
if (!this.adj[v][w] && this.adj[v][w] !== 0) {
this.adj[v].push(w)
this.adj[w].push(v)
this.edges++
}
}
}
深度优先搜索是你访问过的顶点，会接着你访问的顶点继续访问，他不会一次访问完你的邻接数组。比如说1的邻接数组是[2,4,6]，2的邻接数组是[3,5]，它在访问完2之后，不会继续访问4，而是直接访问2的邻接数组3，如果标记过的会直接跨过，依次运行。
dfs(v = 0) {
this.marked[v] = true
if (this.adj[v] !== undefined) {
this.adj[v].forEach(item => {
if (!this.marked[item]) {
this.dfs(item)
}
})
}
}
广度优先搜索会首先访问完你的邻接数组，然后在你邻接数组的第一个元素，依次访问它的邻接数组。
比如我添加以下边：
const lessons = ['Pa', 'Pb', 'Pc','Pd', 'Pe','Pf']
const g = new Graph(lessons, false)
g.addEdge(1, 2)
g.addEdge(0, 5)
g.addEdge(1, 3)
g.addEdge(2, 4)
g.addEdge(0, 1)
形成的邻接数组是：
console.log('this.adj')
//这是一个二维数组，每个数组的下标是一个顶点，值是邻接数组
adj=[
[ 1 , 5 ], //0:[1,5]
[ 2 , 3 ], //1:[2,3]
[ 1 ], //2:[1],
[ 1 ], //3:[1]
[ 2 ], //4:[2]
[ 0 ] //5:[0]
]
//广度优先搜索
bfs(s = 0) {
this.resetMarked()//清楚标记
const queue = []
this.marked = true
queue.push(s) // 添加到队尾
while (queue.length > 0) {
const v = queue.shift() // 从队首移除
if (this.adj[v] !== undefined) {
console.log(`Visited: ${v}`)
// 遍历访问与v的邻接表中其他没有被访问的顶点
this.adj[v].forEach(item => {
if (!this.marked[item]) {
// 保存 item => v 的边
this.edgeTo[item] = v
// 将 item 标记为已访问
this.marked[item] = true
queue.push(item)
}
})
}
}
}
// 重置所有顶点为未访问过
resetMarked() {
for (let i = 0; i < this.vertices; i++) {
this.marked = false
}
}
那我们打印出来的应该是：
Visited:0
Visited:5
Visited:1
Visited:2
Visited:3
Visited:4
这就是广度优先搜索。
最短路径的实现，需要有一个前提条件就是边的存储edgeTo,在我们实现搜索的时候，把边存储在edgeTo数组中，所以我们在实现的时候，先执行一下广度优先搜索，当然你也可以在添加边的时候存储；
获取最短路径，我们默认以0开始，通过pathTo(4)的方式，来获取0=>4的最短路径。
首先我们获取到存储的边：
// 存储的边edgeTo，下标和值均为顶点
edgeTo=[
undefined,
1:0,
2:1,
3:1,
4:2,
5:0
]
思路就是，先找到4,再找到2，直到0。
// 获取最短路径
pathTo(v) {
this.bfs()
let source = 0
if (!this.marked[v]) return undefined
const path = []
let i = v
while (i !== source) {
if (this.edgeTo !== undefined) {
path.push(i)
i = this.edgeTo
} else {
i = source
}
}
path.push(source)
this.resetMarked()
return path.reverse()
}
// [0,1,2,4]
拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。
// 拓扑排序
topSort() {
const stack = []
const visited = []
for (let i = 0; i < this.vertices; i++) {
visited = false
}
for (let i = 0; i < this.vertices; i++) {
if (!visited) {
this.topSortHelper(i, visited, stack)
}
}
for (let i = stack.length - 1; i >= 0; i--) {
if (stack !== undefined) {
console.log(this.vertexList[stack])
}
}
}
// 拓扑排序辅助函数
// 将当前顶点标记为已访问，
//然后递归地访问当前顶点邻接表中每个相邻顶点，标记这些顶点为已访问。
// 最后将当前顶点压入栈
topSortHelper(v, visited, stack) {
visited[v] = true
this.adj[v].forEach(item => {
if (!visited[item]) {
this.topSortHelper(item, visited, stack)
}
})
stack.push(v)
}
// 拓扑排序
Pa
Pb
Pd
Pc
Pe
Pf
自检清单：
变量和类型
原型与原型链
原作用域和闭包
执行机制
[h1]语法和API 手写轮子[/h1] |
|
转播
