学习《JavaScript 数据结构与算法》读书笔记

9 图

9.1 图的相关术语

图是网络结构的抽象模型。图是一组由边连接的节点（或顶点）。

一个图G=(V, E)由以下元素组成
V: 一组顶点
E: 一组边，连接V中的顶点

由一条边连接在一起的顶点称为相邻顶点。比如，A和B是相邻的，A和D是相邻的，A和C是相邻的，A和E不是相邻的。

一个顶点的度是其相邻顶点的数量。比如，A和其他三个顶点相连接，因此，A的度为3；E和其他两个顶点项链，因此，E的度为2。

路径的顶点v1, v2, … , vk的一个连续序列，其中vi和vi+1是相邻的。

简单路径要求不包含重复的顶点。除去最后一个顶点（因为它和第一个顶点是同一个顶点），环也是一个简单路径。

如果图中不存在环，则称该图是无环的。如果图中每两个顶点都存在路径，则该图是连通的。

有向图和无向图

图可以是无向的（边没有方向）或是有向的。有向图的边有一个方向。

如果图中每两个顶点间在双向上都存在路径，则该图是强连通的。

图还可以是未加权的或是加权的，加权图的边被赋予了权值。

我们可以使用图来解决计算机科学世界中的很多问题，比如搜索图中的一个特定顶点或搜索一条待定边，寻找图中的一条路径（从一个顶点到另一个顶点），寻找两个顶点之间的最短路径，以及环检测。

9.2 图的表示

从数据结构的角度来说，我们有多种方式来表示图。在所有的表示法中，不存在绝对正确的方式。图的正确表示法取决于待解决的问题和图的类型。

9.2.1 邻接矩阵

图最常见的实现是邻接矩阵。每个节点都和一个整数相关联，该整数将作为数组的索引，我们用一个二维数组来表示顶点之间的连接。如果索引为i的节点和索引为j的节点相邻，则 array[i][j] === 1 ，否则 array[i][j] === 0。

不是强连通的图（稀疏图）如果用邻接矩阵来表示，则矩阵中将会有很多0，这意味着我们浪费了计算机存储空间来表示根本不存在的边。例如，找给定顶点的相邻顶点，即使该顶点只有一个相邻顶点，我们也不得不迭代一整行。邻接矩阵表示法不够好的另一个理由是，图中顶点的数量可能会改变，而2维数组不太灵活。

9.2.2 邻接表

我们也可以使用一种叫作邻接表的动态数据结构来表示图。邻接表由图中每个顶点的相邻顶点列表所组成。存在好几种方式来表示这种数据结构。我们可以用列表（数组）、链表，甚至是散列表或是字典来表示相邻顶点列表。

尽管邻接表可能对大多数问题来说都是更好的选择，但以上两种表示法都很有用，且它们有着不同的性质（例如，要找出顶点v和w是否相邻，使用邻接矩阵会比较快）。

9.2.3 关联矩阵

我们还可以用关联矩阵来表示图、在关联矩阵中，矩阵的行表示顶点，列表示边。我们使用二维矩阵来表示两者之间的连通性，如果顶点v是边e
的入射点，则 array[v][e] === 1 ;否则 array[v][e] === 0 。

关联矩阵通常用于边的数量比顶点多的情况下，以节省空间和内存。

9.3 创建Graph类

1
2
3
4
5
6
function Graph() {
	/* 我们使用一个数组来存储图中所有顶点的名字 */
	var vertices = [];
	/* 以及一个字典来存储邻接表 */
	var adjList = new Dictionary();
}
1
2
3
4
this.addVertex = function(v) {
	vertices.push(v);
	adjList.set(v, []);
};
1
2
3
4
this.addEdge = function(v, w) {
	adjList.get(v).push(w);
	adjList.get(w).push(v);
};
1
2
3
4
5
6
7
8
9
10
11
12
this.toString = function() {
	var s = '';
	for (var i = 0; i < vertices.length; i++) {
		s += vertices[i] + ' -> ';
		var neighbors = adjList.get(vertices[i]);
		for (var j = 0; j < neighbors.length; j++) {
			s += neighbors[j] + ' ';
		}
		s += '\n';
	}
	return s;
};

测试下面这段代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var graph = new Graph();
var myVertices = ['A','B','C','D','E','F','G','H','I'];
for (var i = 0; i < myVertices.length; i++) {
	graph.addVertex(myVertices[i]);
}
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());
1
2
3
4
5
6
7
8
9
A -> B C D
B -> A E F
C -> A D G
D -> A C G H
E -> B I
F -> B
G -> C D
H -> D
I -> E

9.4 图的遍历

和树数据结构类似，我们可以访问图的所有节点，有两种算法可以对图进行遍历：广度优先搜索（Breadth-First Search, BFS） 和 深度优先搜索（Depth-First Search, DFS）。图遍历可以用来寻找特定的顶点或寻找两个顶点之间的路径，检查图是否连通，检查图是否含有环等。

图遍历算法的思想是必须最总每一个第一次访问的节点，并且追踪有哪些节点还没有被完全探索。对于两种图遍历算法，都需要明确指出第一个被访问的顶点。

完全探索一个顶点要求我们查看该顶点的每一条边。对于每一条边所连接的没有被访问过的顶点，将其标注为被发现的，并将其加进待访问顶点列表中。

为了保证算法的效率，务必访问每个顶点至多两次。连通图中每条边和顶点都会被访问到。

广度优先搜索算法和深度优先搜索算法基本上是相同的，只有一点不同，那就是待访问顶点列表的数据结构。

算法 数据结构 描述
深度优先搜索 栈 通过将顶点存入栈中，顶点是沿着路径被搜索的，存在新的相邻顶点就去访问
广度优先搜索 队列 通过将顶点存入队列中，最先入队列的顶点先被探索

当要标注已经访问过的顶点时，我们用三种颜色来反映它们的状态。

白色： 表示该顶点还没有被访问
灰色： 表示该顶点被访问过，但并未被探索过
黑色： 表示该顶点被访问过且被完全探索过

这就是之前提到的务必访问每个顶点最多两次的原因。

9.4.1 广度优先搜索

广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问图的一层。换句话说，就是先宽厚深地访问顶点。

以下是从顶点 v 开始的广度优先搜索算法所遵循的步骤：

创建一个队列 Q

将 v 标注为被发现的（灰色），并将 v 入队列 Q

如果 Q 非空，则运行以下步骤

将 u 从 Q 中出队列

将标注 u 为被发现的（灰色）

将 u 所有未被访问过的邻点（白色）入队列

将 u 标注为已被探索的（黑色）

1
2
3
4
5
6
7
var initializeColor = function() {
	var color = [];
	for (var i = 0; i < vertices.length; i++) {
		color[vertices[i]] = 'white';
	}
	return color;
};
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
this.bfs = function(v, callback) {
	/* 将color数组初始化为white */
	var color = initializeColor();
	/* 声明和创建一个Queue实例 */
	queue = new Queue();
	/* bfs接受一个顶点作为算法的起始点，将次顶点入队列 */
	queue.enqueue(v);

	/* 如果非空 */
	while (!queue.isEmpty()) {
		/* 从队列中移除一个顶点 */
		var u = queue.dequeue(),
			/* 取得一个包含其所有邻点的邻接表 */
			neighbors = adjList.get(u);
			/* 该顶点被标注为grey，表示已发现（但还未完成探索） */
			color[u] = 'grey';
		/* 对于u的每个邻点 */
		for (var i = 0; i < neighbors.length; i++) {
			/* 取值（该顶点的名字） */
			var w = neighbors[i];
			/* 如果还未被访问过 */
			if (color[w] === 'white') {
				/* 标注为grey */
				color[w] = 'grey';
				/* 并将这个顶点加入队列中 */
				queue.enqueue(w);
			}
		}
		/* 当完成探索该顶点和其邻点后，标注为black（已探索过的） */
		color[u] = 'black';
		if (callback) {
			callback(u);
		}
	}
};
1
2
3
4
function printNode(value) {
	console.log('Visited vertex: ' + value);
}
graph.bfs(myVertices[0], printNode)
1
2
3
4
5
6
7
8
9
Visited vertex: A
Visited vertex: B
Visited vertex: C
Visited vertex: D
Visited vertex: E
Visited vertex: F
Visited vertex: G
Visited vertex: H
Visited vertex: I

1. 使用BFS寻找最短路径

给定一个图G和源顶点v，找出对每个顶点u，u和v之间最短路径的距离（以边的数量计）
对于给定顶点v，广度优先算法会访问所有与其距离为1的顶点，接着是距离为2的顶点，以此类推。因此可以用广度优先算法来解这个问题。可以修改bfs方法以返回给我们一些信息

从v到u的距离d[u]

前溯点pred[u]，用来推导出从v到其他每个顶点u的最短路径

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
this.BFS = function(v) {
	var color = initializeColor(),
		queue = new Queue(),
		/* 声明数组d表示距离 */
		d = [],
		/* 前溯点 */
		pred = [];
	queue.enqueue(v);
	for (var i = 0; i < vertices.length; i++) {
		/* 用0初始化数组d */
		d[vertices[i]] = 0;
		/* 用null初始化数组pred */
		pred[vertices[i]] = null;
	}

	while (!queue.isEmpty()) {
		var u = queue.dequeue(),
			neighbors = adjList.get(u);
		color[u] = 'grey';
		for (i = 0; i < neighbors.length; i++) {
			var w = neighbors[i];
			if (color[w] === 'white') {
				color[w] = 'grey';
				/* 给d[u]加1来设置v和w之间的距离 */
				d[w] = d[u] + 1;
				/* 当发现顶点u的邻点w，设置w的前溯点为u */
				pred[w] = u;
				queue.enqueue(w);
			}
		}
		color[u] = 'black';
	}
	return {
		distances: d,
		predecessors: pred
	}
};
1
2
var shortestPathA = graph.BFS(myVertices[0]);
console.log(shortestPathA);
1
2
distances: [A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2 , I: 3],
predecessors: [A: null, B: "A", C: "A", D: "A", E: "B", F: "B", G: "C", H: "D", I: "E"]

通过前溯点数组，我们可以用下面这段代码来构建从顶点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
/* 用顶点A作为源顶点 */
var fromVertex = myVertices[0];
/* 其他顶点 */
for (var i = 1; i < myVertices.length; i++) {
	/* 从顶点数组得到toVertex */
	var toVertex = myVertices[i],
		/* 创建一个栈来存储路径值 */
		path = new Stack();
	/* 追溯toVertex到fromVertex的路径 */
	/* 变量v被赋值为其前溯点的值，这样我们能够方向追溯这条路径 */
	for (var v = toVertex; v !== fromVertex; v = shortestPathA.predecessors[v]) {
		/* 将变量v添加到栈中 */
		path.push(v);
	}
	/* 最后源顶点也会被添加到栈中，以得到完整路径 */
	path.push(fromVertex);
	/* 创建一个s字符串，并将源顶点赋值给它 */
	/* 它是最后一个加入栈中的， 所以它是第一个被弹出的项 */
	var s = path.pop();
	/* 如果非空 */
	while (!path.isEmpty()) {
		/* 从栈中移出一个项并将其拼接到字符串s的后面 */
		s += ' - ' + path.pop();
	}
	console.log(s);
}
1
2
3
4
5
6
7
8
A - B
A - C
A - D
A - B - E
A - B - F
A - C - G
A - D - H
A - B - E - I

这样，我们得到了从顶点A到图中其他顶点的最短路径（衡量标准是边的数量）

2.深入学习最短路径算法

本章中的图不是加权图。如果要计算加权图中的最短路径（例如，城市A和城市B之间的最短路径：GPS和Google Maps中用到的算法），广度优先搜索未必合适。

举些例子，Dijkstra算法解决了单源最短路径问题。Bellman-Ford算法解决了边权值为负的单源最短路径问题。A*搜索算法解决了求仅一对顶点间的最短路径问题，它用经验法则来加速搜索过程。Floyd-Warshall算法解决了求所有顶点对间的最短路径这一问题。

9.4.2 深度优先搜索

深度优先搜算法将会从第一个指定的顶点开始遍历图，沿着路径知道这条路径最后一个顶点被访问了，接着原路退回并探索下一条路径。换句话说，它是先深度后广度的访问顶点。

深度优先搜索算法不需要一个源顶点。在深度优先搜索算法中，若图中顶点v未访问，则访问改顶点v

标注v为被发现的（灰色）

对于v的所有未访问的邻点w，访问顶点w，标注v为已被探索的（黑色）

深度优先搜索的步骤是递归的，这意味着深度优先搜索算法使用栈来存储函数调用（由递归调用所创建的栈）。

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
this.dfs = function(callback) {
	/*首先创建颜色数组*/
	var color = initializeColor();

	for (var i = 0; i < vertices.length; i++) {
		/* 对于图实例中每一个未被访问过的顶点 */
		if (color[vertices[i]] === 'white') {
			/* 调用私有的递归函数，传递的参数为顶点，颜色数组以及回调函数 */
			dfsVisit(vertices[i], color, callback);
		}
	}
};

var dfsVisit = function(u, color, callback) {
	color[u] = 'grey';
	if (callback) {
		callback(u);
	}
	var neighbors = adjList.get(u);
	for (var i = 0; i < neighbors.length; i++) {
		var w = neighbors[i];
		if (color[w] === 'white') {
			dfsVisit(w, color, callback);
		}
	}
	color[u] = 'black';
};
1
graph.dfs(printNode);
1
2
3
4
5
6
7
8
9
Visited vertex: A
Visited vertex: B
Visited vertex: E
Visited vertex: I
Visited vertex: F
Visited vertex: C
Visited vertex: D
Visited vertex: G
Visited vertex: H

1.探索深度优先算法

对于给定的图G，我们希望深度优先算法搜索算法遍历图G的所有节点，构建“森林”（有根树的一个集合）以及一组源顶点（根），并输出两个数组：发现时间和完成探索实践。我们可以修改dfs方法来返回给我们一些信息

顶点u的发现时间d[u]

当顶点u被标注为黑色时，u的完成探索实践f[u]

顶点u的前溯点p[u]

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
var time = 0;
this.DFS = function() {
	var color = initializeColor(),
		d = [],
		f = [],
		p = [],
		time = 0;

	for (var i = 0; i < vertices.length; i++) {
		f[vertices[i]] = 0;
		d[vertices[i]] = 0;
		p[vertices[i]] = null;
	}
	for (i = 0; i < vertices.length; i++) {
		if (color[vertices[i]] === 'white') {
			DFSVisit(vertices[i], color, d, f, p);
		}
	}
	return {
		discovery: d,
		finished: f,
		predecessors: p
	};
};

var DFSVisit = function(u, color, d, f, p) {
	console.log('discovered' + u);
	color[u] = 'grey';
	/* 当一个顶点第一次被发现时，我们追踪其发现时间 */
	d[u] = ++time;
	var neighbors = adjList.get(u);
	for (var i = 0; i < neighbors.length; i++) {
		var w = neightbors[i];
		if (color[w] === 'white') {
			/* 当它是由引自顶点u的边而被发现的，我们追踪它的前溯点 */
			p[w] = u;
			DFSVisit(w, color, d, f, p);
		}
	}
	color[u] = 'black';
	/* 当这个顶点被完全探索后，我们追踪其完成时间 */
	f[u] = ++time;
	console.log('explored' + u);
};

深度优先算法思想：边是从最近发现的顶点u处被向外探索的。只有连接到未发现的顶点的边被搜索了。当u所有的边都被探索了，该算法回退到u被发现的地方去探索其他的边。这个过程持续到我们发现了所有从原始顶点能够触及的顶点。如果还留有任何其他未被发现的顶点，我们对新源顶点重复这个过程。重复个算法，直到图中所有顶点都被探索了。

对于改进过的深度优先算法，有两点需要注意

时间time变量值的范围只可能在图顶点数量的一倍到两倍之间

对于所有的顶点u，d[u] < f[u]（意味着，发现时间的值比完成事件的值小，完成事件意思是所有顶点都已经被探索过了）。

在这两个假设下，我们有如下的规则：
1 <= d[u] < f[u] <= 2|V|

2.拓扑排序 使用深度优先搜索

有向无环图（DAG）

当我们需要编排一些任务或步骤的执行顺序时，这称为拓扑排序（topological sorting，亦写作topsrt或toposort）

拓扑排序只能应用于DAG

1
2
3
4
5
6
7
8
9
10
11
12
graph = new Graph();
myVertices = ['A','B','C','D','E','F'];
for (i=0; i<myVertices.length; i++){
 graph.addVertex(myVertices[i]);
}
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('B', 'D');
graph.addEdge('B', 'E');
graph.addEdge('C', 'F');
graph.addEdge('F', 'E');
var result = graph.DFS();

执行改进版本的深度优先搜索算法，以倒序来排序完成事件数组

1
B - A - D - C - F - E

这个拓扑排序结果仅是多种可能性之一。如果稍微修改一下算法，就会有不同的结果

1
A - B - C - D - F - E

这也是众多其他可能性中的一个

9.5 最短路径算法

9.5.1 Dijkstra 算法

Dijkstra算法是一种计算从单个源到所有其他源的最短路径的贪心算法。

首先先声明图的邻接矩阵

1
2
3
4
5
6
7
8
var graph = [
	[0, 2, 4, 0, 0, 0],
	[0, 0, 1, 4, 2, 0],
	[0, 0, 0, 0, 3, 0],
	[0, 0, 0, 0, 0, 2],
	[0, 0, 0, 3, 0, 2],
	[0, 0, 0, 0, 0, 0]
];

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
this.dijkstra = function(src) {
	var dist = [],
		visited = [],
		length = this.graph.length;

	for (var i = 0; i < length; i++) {
		/* 把所有的距离（dist）初始化为无限大（JavaScript最大的数 INF = Number.MAX_SAFE_INTEGER） */
		dist[i] = INF;
		/* 将visited初始化为false */
		visited[i] = false;
	}
	/* 把源顶点到自己的距离设为0 */
	dist[src] = 0;

	/* 找出到其余顶点的最短路径 */
	for (var i = 0; i < length - 1; i++) {
		/* 为此，需要从尚未处理的顶点中选出距离最近的顶点 */
		var u = minDistance(dist, visited);
		/* 把选出的点标为true，以免重复计算 */
		visited[u] = true;

		for (var v = 0; v < length; v++) {
			/* 如果找到更短的路径，则更新最短路径的值 */
			if (!visited[v] && this.graph[u][v] !== 0 && dist[u] !== INF && dist[u] + this.graph[u][v] < dist[v]) {
				/* 处理完所有顶点之后，返回从源顶点（src）到图中其他顶点最短路径的结果 */
				dist[v] = dist[u] + this.graph[u][v];
			}
		}
	}
	return dist;
}

要计算顶点间的minDCistance，就要搜索dist数组中的最小值，返回它在数组中的索引：

1
2
3
4
5
6
7
8
9
10
11
12
var minDistance = function(dist, visited) {
	var min = INF,
		minIndex = -1;

	for (var v = 0; v < dist.length; v++) {
		if (visited[v] === false && dist[v] <= min) {
			min = dist[v];
			minIndex = v;
		}
	}
	return minIndex;
};

对本节开始的图执行以上算法，会得到如下输出

1
2
3
4
5
6
0 0
1 2
2 3
3 6
4 4
5 6

也可以修改算法，将最短路径的值和路径一同返回

9.5.2 Floyd-Warshall算法

Floyd-Warshall算法是一种计算图中所有最短路径的动态规划算法。通过该算法，我们可以找出所有源到所有顶点的最短路径

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
this.floydWarshall = function() {
	var dist = [],
		length = this.graph.length,
		i,
		j,
		k;

	/* 把dist数组初始化为每个顶点之间的权值 */
	for (i = 0; i < length; i++) {
		dist[i] = [];
		for (j = 0; j < length; j++) {
			dist[i][j] = this.graph[i][j];
		}
	}
	
	/* 通过k，得到i途径顶点0至k，到达j的最短路径 */
	for (k = 0; k < length; k++) {
		for (i = 0; i < length; i++) {
			for (j = 0; j < length; j++) {
				/* 判断i经过顶点k到达j的路径是否比已有的最短路径更短 */
				if (dist[i][k] + dist[k][j] < dist[i][j]) {
					/* 如果是更短的路径，更新 */
					dist[i][j] = dist[i][k] + dist[k][j];
				}
			}
		}
	}
	return dist;
};

对本节开始的图执行以上算法，会得到如下输出

1
2
3
4
5
6
0   2   3   6   4   6
INF 0   1   4   2   4
INF INF 0   6   3   5
INF INF INF 0   INF 2
INF INF INF 3   0   2
INF INF INF INF INF 0

9.6 最小生成树

最小生成树（MST）

9.6.1 Prim算法

Prim算法是一种求解加权无向连通图的MST问题的贪心算法，它能找出一个边的子集，使得其构成的树包含图中的所有顶点，且边的权值之和最小

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
this.prim = function() {
	var parent = [],
		key = [],
		visited = [],
		i;
	length = this.graph.length,

	for (i = 0; i < length; i++) {
		/* 把所有顶点（key）初始化为无限大 */
		key[i] = INF;
		/* 把visited[]初始化为false */
		visited[i] = false;
	}
	/* 选择第一个key作为第一个顶点 */
	key[0] = 0;
	/* 因为第一个顶点总是MST的根节点，所以为-1 */
	parent[0] = -1;

	for (i = 0; i < length - 1; i++) {
		/* 从未处理的顶点集合中选出key值最小的顶点（和Digkstra一样） */
		var u = minKey(key, visited);
		/* 防止重复计算 */
		visited[u] = true;

		for (var v = 0; v < length; v++) {
			/* 如果得到更小的权值 */
			if (this.graph[u][v] && visited[v] === false && this.graph[u][v] < key[v]) {
				/* 保存MST路径 */
				parent[v] = u;
				/* 更新其权值 */
				key[v] = this.graph[u][v];
			}
		}
	}
	/* 返回包含MST的结果 */
	return parent;
};

对上节开始的图执行以上算法，会得到如下输出

1
2
3
4
5
6
Edge  Weight
0 - 1 2
1 - 2 2
5 - 3 2
1 - 4 2
4 - 5 2

9.6.2 Kruskal 算法

和Prim算法类似，Kruskal算法也是一种求加权无向连通图的MST的贪心算法。

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
this.kruskal = function() {
	var length = this.graph.length,
		parent = [],
		cost,
		ne = 0,
		a,
		b,
		u,
		v,
		i,
		j,
		min;

	/* 把邻接矩阵的值复制个cost数组 */
	cost = initializeCost();

	/* 当MST的边数小于顶点总数减1时 */
	while (ne < length - 1) {
		/* 找出权值最小的边 */
		for (i = 0; min = INF; i < length; i++) {
			for (j = 0; j < length; j++) {
				if (cost[i][j] < min) {
					min = cost[i][j];
					u = i;
					v = j;
				}
			}
		}

		/* 检查MST中是否已存在这条边，以避免环路 */
		u = find(u, parent);
		v = find(v, parent);

		/* 如果u和v是不同的边，则将其加入MST */
		if (union(u, v, parent)) {
			ne++;
		}

		/* 从列表中移除这些边，以免重复计算 */
		cost[u][v] = cost[v][u] = INF;
	}
	return parent;
}

下面是find函数的定义。它能防止MST出现环路

1
2
3
4
5
6
var find = function(i, parent) {
	while (parent[i]) {
		i = parent[i];
	}
	return i;
};

union函数定义如下

1
2
3
4
5
6
7
var union = function(i, j, parent) {
	if (i !== j) {
		parent[j] = i;
		return true;
	}
	return false;
};