# 图
- 图中的元素我们就叫做顶点(vertex)
- 图中的一个顶点可以与任意其他顶点建立连接关系。我们把这种建立的关系叫做边(edge)
- 跟顶点相连接的边的条数,就叫做顶点的度(degree)
- 我们把这种边有方向的图叫做“有向图”
- 我们把边没有方向的图就叫做“无向图”
- 在有向图中,我们把度分为入度(In-degree)和出度(Out-degree)
- 带权图,每条边都有一个权重(weight)
- 图最直观的一种存储方法就是,邻接矩阵(Adjacency Matrix)
- 另外一种图的存储方法,邻接表(Adjacency List)
# 广度优先搜索(BFS)
- 广度优先搜索(Breadth-First-Search),我们平常都简称 BFS。
- 直观地讲,它其实就是一种“地毯式”层层推进的搜索策略,即先查找离起始顶点最近的,然后是次近的,依次往外搜索
- 借助一个队列实现深度优先搜索
- 三个重要的辅助变量 visited、queue、prev
visited 是用来记录已经被访问的顶点,用来避免顶点被重复访问 queue 是一个队列,用来存储已经被访问、但相连的顶点还没有被访问的顶点 prev 用来记录搜索路径
使用对象模拟图
/*
a —— b —— g
| | \
d —— e —— c
| |
f h
*/
let graph = {
a: ['b', 'd'],
b: ['a', 'e', 'c', 'g'],
c: ['b', 'e'],
d: ['a', 'e', 'f'],
e: ['b', 'd', 'c', 'h'],
f: ['d'],
h: ['e'],
g: ['b']
}
// 广度优先搜索
function bfs(graph, vertex, visited = [], queue = [], prev = []) {
visited.push(vertex) // 设置当前顶点访问
let ver = graph[vertex] // 获取当前顶点的所有邻接点
queue = ver
while (queue.length) {
for (let i = 0; i < ver.length; i++) {
// 没访问过的点push,避免重复
if (!visited.includes(ver[i])) {
visited.push(ver[i])
queue.push(ver[i])
prev.push(`${vertex}->${ver[i]}`)
}
}
// 类似树的层次遍历
vertex = queue.shift()
ver = graph[vertex]
}
return [prev.join(), visited.join()]
}
console.log(bfs(graph, 'a'));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 深度优先搜索(DFS)
- 深度优先搜索(Depth-First-Search),简称 DFS
- 深度优先搜索用的是一种比较著名的算法思想,回溯思想
- 深度优先搜索算法的消耗内存主要是 visited、prev 数组和递归调用栈
- 借助一个栈实现深度优先搜索
/*
a —— b —— g
| | \
d —— e —— c
| |
f h
*/
let graph = {
a: ['b', 'd'],
b: ['a', 'e', 'c', 'g'],
c: ['b', 'e'],
d: ['a', 'e', 'f'],
e: ['b', 'd', 'c', 'h'],
f: ['d'],
h: ['e'],
g: ['b']
}
// 深度优先搜索
function dfs(graph, vertex, visited = [], prev = []) {
if (visited.includes(vertex)) return
visited.push(vertex)
let ver = graph[vertex]
for (let i = 0; i < ver.length; i++) {
// 没访问过的点push,避免重复
if (!visited.includes(ver[i])) {
prev.push(`${vertex}->${ver[i]}`)
dfs(graph, ver[i], visited, prev) // 使用递归就能模拟栈
}
}
return [prev.join(), visited.join()]
}
console.log(dfs(graph, 'g'));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 拓扑排序
- 拓扑排序本身就是基于有向无环图的一个算法
拓扑排序有两种实现方法:Kahn 算法和 DFS 深度优先搜索算法
Kahn算法:
- 实际上用的是贪心算法思想
- 定义数据结构的时候,如果 s 需要先于 t 执行,那就添加一条 s 指向 t 的边。所以,如果某个顶点入度为 0, 也就表示,没有任何顶点必须先于这个顶点执行,那么这个顶点就可以执行了
DFS 深度优先搜索算法:
- 深度优先遍历,遍历图中的所有顶点
- 这个算法包含两个关键部分:
- 第一部分是通过邻接表构造逆邻接表
- 第二部分是这个算法的核心,也就是递归处理每个顶点
拓扑排序还能检测图中环的存在。对于 Kahn 算法来说,如果最后输出出来的顶点个数,少于图中顶点个数,图中还有入度不是 0 的顶点,那就说明,图中存在环
# 最短路径Dijkstra 算法
- 单源最短路径算法(一个顶点到一个顶点)
- 贪心算法
- 我们用 vertexes 数组,记录从起始顶点到每个顶点的距离(dist)。
- 起初,我们把所有顶点的 dist 都初始化为无穷大(也就是代码中的 Integer.MAX_VALUE)。
- 我们把起始顶点的 dist 值初始化为 0,然后将其放到优先级队列中。我们从优先级队列中取出 dist 最小的顶点 minVertex,然后考察这个顶点可达的所有顶点(代码中的 nextVertex)。
- 如果 minVertex 的 dist 值加上 minVertex 与 nextVertex 之间边的权重 w 小于 nextVertex 当前的 dist 值,也就是说,存在另一条更短的路径,它经过 minVertex 到达 nextVertex。
- 那我们就把 nextVertex 的 dist 更新为 minVertex 的 dist 值加上 w。
- 然后,我们把 nextVertex 加入到优先级队列中。重复这个过程,直到找到终止顶点 t 或者队列为空
- predecessor 数组的作用是为了还原最短路径,它记录每个顶点的前驱顶点
- inqueue 数组是为了避免将一个顶点多次添加到优先级队列中
先用堆实现优先队列
// 优先队列
class PriorityQueue {
constructor(sort = 1, queue = []) {
this.queue = queue
this.sort = sort
this.length = queue.length
this.adjust()
}
pqPush(flag, val) {
this.queue.push([flag, val])
this.length++
this.adjust(this.sort)
return this.queue
}
pqShift() {
if (!this.length) return false
const result = this.queue.shift()
this.length--
this.adjust()
return result
}
sortDown(arr, i, length) {
for (let j = i * 2 + 1; j < length; j = j * 2 + 1) {
if (j + 1 < length && (arr[j + 1][1] - arr[j][1]) * this.sort >= 0) j++
if (!((arr[j][1] - arr[i][1]) * this.sort >= 0)) break
arr[i] = [arr[j], arr[j] = arr[i], i = j][0]
}
}
adjust() {
const arr = this.queue
const first = ~~(arr.length / 2 - 1)
for (let i = first; i >= 0; i--) {
this.sortDown(arr, i, arr.length)
}
for (let j = arr.length - 1; j > 0; j--) {
arr[j] = [arr[0], arr[0] = arr[j]][0]
this.sortDown(arr, 0, j)
}
return this.queue
}
getPQ() {
return this.queue
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
构造加权图:
const graph = {
A:{ B:5 , C:1 },
B:{ C:2 , A:5 , D:1 },
C:{ A:1 , B:2 , D:4 , E:8 },
D:{ B:1 , C:4 , E:3 , F:6 },
E:{ C:8 , D:3 },
F:{ D:6 }
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
最短路径:
// 初始化数据
function init_path(graph, start) {
const res = { [start]: 0 }
for (const key of Object.keys(graph)) {
if (key !== start) res[key] = Infinity
}
return res
}
// 最短路径
function minPath(graph, start) {
const pq = new PriorityQueue() // 优先队列,存放所有到达顶点的可能
const vertexes = init_path(graph, start) // 最优路径数组
const predecessor = {
[start]: null
} // 记录前驱
const visited = new Set() // 已访问
pq.pqPush(start, 0)
while (pq.length) {
const vertex = pq.pqShift() // 取一条最短路径节点,可能访问、未访问
const flag = vertex[0],
minLen = vertex[1]
if (visited.has(flag)) continue // 访问过,下一个
// 开始处理未访问的顶点
visited.add(flag)
// vertexes[flag] = minLen // 更新记录表中最短路径,初始Infinity
// 遍历邻接点
for (const key of Object.keys(graph[flag])) {
// 添加没操作过的邻接点
if (!visited.has(key)) {
// 更新当前节点最短路径 = 当前节点与起始节点最短路径 + 2节点路径
const curLen = minLen + graph[flag][key]
if (vertexes[key] > curLen) { // 更新最短路径
vertexes[key] = curLen
predecessor[key] = flag
}
pq.pqPush(key, curLen)
}
}
}
return [vertexes, predecessor]
}
// 测试
const [minLen, prev] = minPath(graph, 'A')
console.log(minLen);
console.log(prev);
// 打印
function printPath(prev, vertex) {
let res = '', queue = [vertex]
const visited = new Set()
while (queue.length) {
vertex = queue.shift()
while (visited.has(vertex)) vertex = queue.shift()
for (const key of Object.keys(prev)) {
if (prev[key] === vertex) {
res += ` ${vertex}->${key} `
queue.push(key)
}
}
visited.add(vertex)
}
return res
}
console.log(printPath(prev, 'A'));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# A*算法
- A* 算法利用贪心算法的思路
- 启发式搜索算法利用估价函数,避免“跑偏”,贪心地朝着最有可能到达终点的方向前进。这种算法找出的路线,并不是最短路线
曼哈顿距离 = |x1-x2|+|y1-y2|
G:当前位置离起始点距离 H:当前位置离目的地距离 F:G+H的距离
// 1表示障碍物,0表示可通行
const graph = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], //0
[1, 0, 0, 0, 0, 0, 1, 0, 0, 1], //1
[1, 0, 0, 0, 1, 0, 1, 0, 0, 1], //2
[1, 0, 1, 0, 1, 0, 0, 1, 0, 1], //3
[1, 0, 0, 0, 1, 0, 1, 1, 0, 1], //4
[1, 1, 1, 0, 1, 0, 0, 0, 1, 1], //5
[1, 0, 1, 0, 1, 0, 1, 0, 1, 1], //6
[1, 0, 1, 0, 0, 1, 1, 0, 0, 1], //7
[1, 0, 0, 0, 0, 0, 1, 0, 0, 1], //8
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1] //9
]//0 1 2 3 4 5 6 7 8 9
// 模拟
/* const graph = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], //0
[1, 0, 0, 8, 8, 8, 1, 0, 0, 1], //1
[1, 8, 8, 8, 1, 8, 1, 0, 0, 1], //2
[1, 0, 1, 0, 1, 8, 0, 1, 0, 1], //3
[1, 0, 0, 0, 1, 8, 1, 1, 0, 1], //4
[1, 1, 1, 0, 1, 8, 8, 8, 1, 1], //5
[1, 0, 1, 0, 1, 0, 1, 8, 1, 1], //6
[1, 0, 1, 0, 0, 1, 1, 8, 0, 1], //7
[1, 0, 0, 0, 0, 0, 1, 8, 0, 1], //8
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1] //9
]//0 1 2 3 4 5 6 7 8 9 */
// 计算曼哈顿距离
function startToEndLen(start, end){
return Math.abs(start[0] - end[0]) + Math.abs(start[1] - end[1])
}
// A* 算法
function aStart(graph, start = [2, 1], end = [8, 7]) {
let H = startToEndLen(start, end) // 距离目的地
let G = startToEndLen(start, start) // 距离起点
let F = G + H
const visited = new Set() // 已经访问点
let [curX, curY] = start
let [endX, endY] = end
let s = `(${start.toString()})`
let predecessor = {[`${curX},${curY}`]:'start'} // 前驱
const path = new PriorityQueue() // 优先队列
path.pqPush([curX, curY, s], F)
// 记录邻接点
function pushPath([curX, curY, s]){
const arr = [
[curX + 1, curY],
[curX - 1, curY],
[curX, curY + 1],
[curX, curY - 1],
]
arr.forEach((v)=>{
let str = `${v[0]},${v[1]}`
if(!visited.has(str)){
if(!predecessor[str])
predecessor[str] = `${curX},${curY}`
H = startToEndLen(v, end)
G = startToEndLen(v, start)
path.pqPush([...v,`${s}->(${str})`], G + H)
}
})
}
// 搜索路径
function search(s){
if(!path.length) return s;
[[curX, curY, s],F] = path.pqShift() // 取当前最优路径
if(curX===endX && curY===endY) return s
if(graph[curX][curY] === 1) return search(s)
visited.add(`${curX},${curY}`) // 添加为访问过
// 添加当前顶点的邻接顶点,排除已经访问,并且计算F权重,添加到优先队列
pushPath([curX, curY, s])
return search(s)
}
return search(s)
}
console.log(aStart(graph))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
# 最小生成树
- 一个有 n 个结点的连通图的生成树是原图的极小连通子图
- 包含原图中的所有 n 个结点,并且有保持图连通的最少的边
const graph = {
A:{ B:5 , C:1 },
B:{ C:2 , A:5 , D:1 },
C:{ A:1 , B:2 , D:4 , E:8 },
D:{ B:1 , C:4 , E:3 , F:6 },
E:{ C:8 , D:3 },
F:{ D:6 }
}
// 最小生成树
function mst(graph) {
const vertexes = new PriorityQueue()
const select = []
for (const [key,val] of Object.entries(graph)) {
for (const [k,v] of Object.entries(val)) {
if(key<k) vertexes.pqPush(`${key}-${k}`,v)
}
}
// 判断图是否有环
function isRing(){
let res = {}
select.forEach((v)=>{
let [f,t] = v.split('-')
if(!res[f]) res[f] = [t,0]
if(!res[t]) res[t] = [f,0]
res[f][1] += 1
res[t][1] += 1
})
for (let i = 0; i < select.length; i++) {
for (const [key,val] of Object.entries(res)) {
if(val[1] === 1){
res[key][1] = 0
res[res[key][0]][1] -= 1
}
}
}
for (const [key,val] of Object.entries(res)) {
if(val[1] > 1) return true
}
return false
}
const len = vertexes.length
while(vertexes.length && select.length<len){
const [s,v] = vertexes.pqShift()
select.push(s)
if(isRing()) select.pop()
}
return select.join(' ')
}
console.log(mst(graph));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49