章节 8 kruskal 算法
最小生成树
kruskal 算法是一种贪婪算法，工作流程如下：
- 创建图中所有的边
- 当以上集合不为空，并且所有的顶点还未覆盖
- 移除集合中最小边
- 检查这条边是否构成一个环或者连接成2颗树，因此需要抛弃这条边，否则的话，把它加入到树当中
- 当上述过程完毕后，就产生了一颗最小生成树
为了实现这个算法，我们需要借助2个数据结构
首先，我们需要先对所有边进行快速排序，以便在每次遍历获取符合要求的边
接着，我们需要不相交的集合，这个集合通常也叫做并查集，用来跟踪集合中的数据元素进入一个不相交的子集合。无论何时，我们增加一个新的节点进入树，我们需要检查它们是否已经存在。如果是，它们有一个环。如果不是，我们需要把这条边的两个顶点做并操作。这样两个顶点都被加入到相同的子集合了。
假设有这样的有权无向图如下：
下面展示具体实现：
//快速排序 数组a由对象组成 key为排序的参照指标 quickSort(0,a.length-1,a,'key')
function quickSort(left, right, a, key) {
if (left > right)
return;
var i = left;
var j = right;
var benchMark = a[i];
var temp;
while (i != j) {
//移动 j
while (a[j][key] >= benchMark[key] && i < j)
j--;
//移动 i
while (a[i][key] <= benchMark[key] && i < j)
i++;
if (i < j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
a[left] = a[i];
a[i] = benchMark;
quickSort(left, i - 1, a, key);
quickSort(i + 1, right, a, key);
}
var MakeSet = (function() {
let set = new Set();
return function(x) {
x.parent = x;
x.rank = 0;
if (!set.has(x)) set.add(x);
return set;
}
})();
class UnionFind {
Find(x) {
if (x.parent != x)
x.parent = Find(x.parent);
return x.parent;
}
Union(u, v) {
let uRoot = this.Find(u);
let vRoot = this.Find(v);
// 如果 u 和 v 在同一颗树
if (uRoot == vRoot) return;
// 如果 u 和 v 不在同一颗树中，合并它们
// 如果 uRoot 的层级比 vRoot 的小,将 uRoot 作为 vRoot 前驱节点
if (uRoot.rank < vRoot.rank) uRoot.parent = vRoot;
// 如果 uRoot 的层级比 vRoot 的大,将 vRoot 作为 uRoot 前驱节点
else if (uRoot.rank > vRoot.rank) vRoot.parent = uRoot;
//任选一个作为根节点
else {
vRoot.parent = uRoot;
uRoot.rank = uRoot.rank + 1;
}
}
}
//顶点
class Vertex {
constructor() {
this.edges = null; //由顶点发出的所有边
this.id = null; //节点的唯一标识
this.data = null; //存放节点的数据
}
}
//数据结构 邻接链表-边
class Edge {
constructor() {
this.index = null; //边所依附的节点的位置
this.sibling = null;
this.w = null; //保存边的权值
}
}
//数据结构 图-G
class Graph {
constructor() {
this.V = []; //节点集
this.E = [];
this.refer = new Map(); //字典 用来映射标节点的识符和数组中的位置
}
initVertex(vertexs) {
//创建节点并初始化节点属性 id
for (let v of vertexs) {
let vertex = new Vertex();
vertex.id = v.id;
this.V.push(vertex);
}
//初始化 字典
for (let i in this.V) {
this.refer.set(this.V[i].id, i);
}
}
createLink(index, len, edges, refer) {
if (index >= len) return null;
let edgeNode = new Edge();
edgeNode.index = refer.get(edges[index].id); //边连接的节点 用在数组中的位置表示 参照字典
edgeNode.w = edges[index].w; //边的权值
edgeNode.sibling = createLink(++index, len, edges, refer); //通过递归实现 回溯
return edgeNode;
}
//建立图中 边 的关系
initEdge(edges) {
for (let field in edges) {
let index = this.refer.get(field); //从字典表中找出节点在 V 中的位置
let vertex = this.V[index]; //获取节点
vertex.edges = this.createLink(0, edges[field].length, edges[field], this.refer);
}
}
storageEdge(edges) {
this.E = edges;
}
}
// kruskal 算法
function Kruskal(G) {
const uf = new UnionFind();
let A = []; //A用于存放最小生成数所包含的边
for(let x of G.V) {
MakeSet(x);
}
//对G.E按照边的权中从小到大排序
for(let e of G.E) {
quickSort(0, G.E.length-1, G.E, 'w');
}
for(let e of G.E) {
let u = G.V[G.refer.get(e.u)];
let v = G.V[G.refer.get(e.v)];
if(uf.Find(u)!=uf.Find(v)) {
A.push(e);
uf.Union(u, v);
}
}
return A;
}
//测试数据
var vertexs = [{id:'a'}, {id:'b'}, {id:'c'}, {id:'d'}, {id:'e'}];
var edges = [
{u:'a',v:'b',w:3},
{u:'a',v:'c',w:1},
{u:'b',v:'a',w:3},
{u:'b',v:'c',w:4},
{u:'b',v:'d',w:5},
{u:'c',v:'a',w:1},
{u:'c',v:'b',w:4},
{u:'c',v:'d',w:6},
{u:'c',v:'e',w:7},
{u:'d',v:'b',w:5},
{u:'d',v:'c',w:6},
{u:'d',v:'e',w:2},
{u:'e',v:'c',w:7},
{u:'e',v:'d',w:6}
]
var g = new Graph();
g.initVertex(vertexs);
g.storageEdge(edges);
var A = Kruskal(g);
console.log(A);
最终的结果输出顺序会是这样：ac,de,ab,bd, 打印结果如下：