資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究JavaScript 中的克魯斯卡爾演算法
克魯斯卡爾演算法是一種貪婪演算法，其工作原理如下：
1. 它建立圖中所有邊的集合。
2. 當上述集合不為空且未覆蓋所有頂點時，
- 它從該集合中移除權重最小的邊
- 它檢查此邊是否形成迴圈或僅連線兩棵樹。如果它形成迴圈，我們丟棄此邊，否則我們將它新增到我們的樹中。
3. 當上述處理完成後，我們就得到了最小生成樹。
為了實現此演算法，我們需要另外兩種資料結構。
首先，我們需要一個優先佇列，我們可以使用它來按排序順序儲存邊，並在每次迭代時獲取所需的邊。
接下來，我們需要一個不相交集資料結構。不相交集資料結構（也稱為聯合查詢資料結構或合併查詢集）是一種資料結構，它跟蹤一組被劃分為多個不相交（不重疊）子集的元素。每當我們將新節點新增到樹中時，我們將檢查它們是否已連線。如果是，則我們有一個迴圈。如果不是，我們將對邊的兩個頂點進行聯合。這會將它們新增到同一子集中。
讓我們看一下 UnionFind 或 DisjointSet 資料結構的實現；
示例
class UnionFind {
constructor(elements) {
// Number of disconnected components
this.count = elements.length;
// Keep Track of connected components
this.parent = {};
// Initialize the data structure such that all
// elements have themselves as parents
elements.forEach(e => (this.parent[e] = e));
}
union(a, b) {
let rootA = this.find(a);
let rootB = this.find(b);
// Roots are same so these are already connected.
if (rootA === rootB) return;
// Always make the element with smaller root the parent.
if (rootA < rootB) {
if (this.parent[b] != b) this.union(this.parent[b], a);
this.parent[b] = this.parent[a];
} else {
if (this.parent[a] != a) this.union(this.parent[a], b);
this.parent[a] = this.parent[b];
}
}
// Returns final parent of a node
find(a) {
while (this.parent[a] !== a) {
a = this.parent[a];
}
return a;
}
// Checks connectivity of the 2 nodes
connected(a, b) {
return this.find(a) === this.find(b);
}
}您可以使用以下方法進行測試：
示例
let uf = new UnionFind(["A", "B", "C", "D", "E"]);
uf.union("A", "B"); uf.union("A", "C");
uf.union("C", "D");
console.log(uf.connected("B", "E"));
console.log(uf.connected("B", "D"));輸出
這將給出以下輸出：
false true
現在讓我們看一下使用此資料結構實現克魯斯卡爾演算法：
示例
kruskalsMST() {
// Initialize graph that'll contain the MST
const MST = new Graph();
this.nodes.forEach(node => MST.addNode(node));
if (this.nodes.length === 0) {
return MST;
}
// Create a Priority Queue
edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
// Add all edges to the Queue:
for (let node in this.edges) {
this.edges[node].forEach(edge => {
edgeQueue.enqueue([node, edge.node], edge.weight);
});
}
let uf = new UnionFind(this.nodes);
// Loop until either we explore all nodes or queue is empty
while (!edgeQueue.isEmpty()) {
// Get the edge data using destructuring
let nextEdge = edgeQueue.dequeue();
let nodes = nextEdge.data;
let weight = nextEdge.priority;
if (!uf.connected(nodes[0], nodes[1])) {
MST.addEdge(nodes[0], nodes[1], weight);
uf.union(nodes[0], nodes[1]);
}
}
return MST;
}您可以使用以下方法進行測試：
示例
let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");
g.addEdge("A", "C", 100);
g.addEdge("A", "B", 3);
g.addEdge("A", "D", 4);
g.addEdge("C", "D", 3);
g.addEdge("D", "E", 8);
g.addEdge("E", "F", 10);
g.addEdge("B", "G", 9);
g.addEdge("E", "G", 50);
g.kruskalsMST().display();輸出
這將給出以下輸出：
A->B, D B->A, G C->D D->C, A, E E->D, F F->E G->B
更新於：2020年6月15日
1K+ 次瀏覽
廣告