Graph [图]
# 介绍
在离散数学中,图(Graph)是用于表示物体与物体之间存在某种关系的结构。数学抽象后的 “物体” 称作节点或顶点(英語:Vertex,node 或 point),节点间的相关关系则称作边。在描绘一张图的时候,通常用一组点或小圆圈表示节点,其间的边则使用直线或曲线。
图中的边可以是有方向或没有方向的。例如在一张图中,如果节点表示聚会上的人,而边表示两人曾经握手,则该图就是没有方向的,因为甲和乙握过手也意味着乙一定和甲握过手。相反,如果一条从甲到乙的边表示甲欠乙的钱,则该图就是有方向的,因为 “曾经欠钱” 这个关系不一定是双向的。前一种图称为无向图,后一种称为有向图。
# 实现
# JavaScript
const { DirectedGraph } = require('./directedGraph');
/**
* @class Graph
* @extends DirectedGraph
*/
class Graph extends DirectedGraph {
/**
* Removes all edges connected to a vertex
* @public
* @override
* @param {number|string} key
* @return {number} number of removedEdgesCount edges
*/
removeEdges(key) {
if (!this.hasVertex(key)) {
return 0;
}
let removedEdgesCount = 0;
this._edges.get(key).forEach((weight, destKey) => {
this.removeEdge(destKey, key);
removedEdgesCount += 1;
});
this._edgesCount -= this._edges.get(key).size;
this._edges.set(key, new Map());
return removedEdgesCount;
}
/**
* Adds an edge between two existing vertices
* @public
* @override
* @param {number|string} srcKey
* @param {number|string} destKey
* @param {number} [weight] - default 1
*/
addEdge(sourceKey, destKey, weight) {
super.addEdge(sourceKey, destKey, weight);
return super.addEdge(destKey, sourceKey, weight);
}
/**
* Removes the connecting edge between two vertices
* @public
* @override
* @param {number|string} srcKey
* @param {number|string} destKey
* @returns {boolean}
*/
removeEdge(sourceKey, destKey) {
super.removeEdge(sourceKey, destKey);
return super.removeEdge(destKey, sourceKey);
}
/**
* Gets the number of edges in the graph
* @public
* @override
* @returns {number}
*/
getEdgesCount() {
return super.getEdgesCount() / 2;
}
}
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
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
或者
class Graph {
constructor () {
this.adjacencyMap = {}
}
addVertex (vertex) {
this.adjacencyMap[vertex] = []
}
containsVertex (vertex) {
return typeof (this.adjacencyMap[vertex]) !== 'undefined'
}
addEdge (vertex1, vertex2) {
if (this.containsVertex(vertex1) && this.containsVertex(vertex2)) {
this.adjacencyMap[vertex1].push(vertex2)
this.adjacencyMap[vertex2].push(vertex1)
}
}
printGraph (output = value => console.log(value)) {
const keys = Object.keys(this.adjacencyMap)
for (const i of keys) {
const values = this.adjacencyMap[i]
let vertex = ''
for (const j of values) {
vertex += j + ' '
}
output(i + ' -> ' + vertex)
}
}
/**
* Prints the Breadth first traversal of the graph from source.
* @param {number} source The source vertex to start BFS.
*/
bfs (source, output = value => console.log(value)) {
const queue = [[source, 0]] // level of source is 0
const visited = new Set()
while (queue.length) {
const [node, level] = queue.shift() // remove the front of the queue
if (visited.has(node)) { // visited
continue
}
visited.add(node)
output(`Visited node ${node} at level ${level}.`)
for (const next of this.adjacencyMap[node]) {
queue.push([next, level + 1]) // level 1 more than current
}
}
}
/**
* Prints the Depth first traversal of the graph from source.
* @param {number} source The source vertex to start DFS.
*/
dfs (source, visited = new Set(), output = value => console.log(value)) {
if (visited.has(source)) { // visited
return
}
output(`Visited node ${source}`)
visited.add(source)
for (const neighbour of this.adjacencyMap[source]) {
this.dfs(neighbour, visited, output)
}
}
}
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
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
或者:
class Graph {
constructor () {
this.adjacencyObject = {}
}
addVertex (vertex) {
if (!this.adjacencyObject[vertex]) this.adjacencyObject[vertex] = []
}
addEdge (vertex1, vertex2) {
this.adjacencyObject[vertex1].push(vertex2)
this.adjacencyObject[vertex2].push(vertex1)
}
removeEdge (vertex1, vertex2) {
this.adjacencyObject[vertex1] = this.adjacencyObject[vertex1].filter(
(v) => v !== vertex2
)
this.adjacencyObject[vertex2] = this.adjacencyObject[vertex2].filter(
(v) => v !== vertex1
)
}
removeVertex (vertex) {
while (this.adjacencyObject[vertex].length) {
const adjacentVertex = this.adjacencyObject[vertex].pop()
this.removeEdge(vertex, adjacentVertex)
}
}
/**
* Return DFS (Depth First Search) List Using Recursive Method
*/
DFS (start) {
if (!start) return null
const result = []
const visited = {}
const adjacencyObject = this.adjacencyObject
function dfs (vertex) {
if (!vertex) return null
visited[vertex] = true
result.push(vertex)
adjacencyObject[vertex].forEach((neighbor) => {
if (!visited[neighbor]) {
dfs(neighbor)
}
})
}
dfs(start)
return result
}
/**
* Return DFS(Depth First Search) List Using Iteration
*/
DFSIterative (start) {
if (!start) return null
const stack = [start]
const visited = {}
visited[start] = true
const result = []
let currentVertex
while (stack.length) {
currentVertex = stack.pop()
result.push(currentVertex)
this.adjacencyObject[currentVertex].forEach((neighbor) => {
if (!visited[neighbor]) {
visited[neighbor] = true
stack.push(neighbor)
}
})
}
return result
}
BFS (start) {
if (!start) return null
const queue = [start]
const visited = {}
visited[start] = true
let currentVertex
const result = []
while (queue.length) {
currentVertex = queue.shift()
result.push(currentVertex)
this.adjacencyObject[currentVertex].forEach((neighbor) => {
if (!visited[neighbor]) {
visited[neighbor] = true
queue.push(neighbor)
}
})
}
return result
}
}
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
# 参考
编辑 (opens new window)
上次更新: 2022/10/13, 15:33:21