資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時裝研究
法律克魯斯卡爾（最小生成樹）MST演算法
G(V,E)是有連線的圖，且給定了每條邊的權重或代價。克魯斯卡爾演算法將使用此圖和代價找出最小生成樹。
該演算法採用合併樹的方法。最初，有多棵不同的樹，此演算法將透過選取代價最小的邊將這些樹合併，形成一棵獨立的樹。
在這個問題中，列出所有邊，並根據其代價進行排序。從列表中，選出代價最小的邊新增到樹中，並檢查每條邊是否形成了迴路，如果形成了迴路，則從列表中捨棄該邊，然後查詢下一條邊。
此演算法的時間複雜度為O(E log E)或O(E log V)，其中E是邊的數量，V是頂點的數量。
輸入 - 鄰接矩陣
0 1 3 4 ∞ 5 ∞ 1 0 ∞ 7 2 ∞ ∞ 3 ∞ 0 ∞ 8 ∞ ∞ 4 7 ∞ 0 ∞ ∞ ∞ ∞ 2 8 ∞ 0 2 4 5 ∞ ∞ ∞ 2 0 3 ∞ ∞ ∞ ∞ 4 3 0
輸出 -
Edge: B--A And Cost: 1 Edge: E--B And Cost: 2 Edge: F--E And Cost: 2 Edge: C--A And Cost: 3 Edge: G--F And Cost: 3 Edge: D--A And Cost: 4 Total Cost: 15
演算法
kruskal(g: 圖，t: 樹)
輸入 - 給定的圖g和一棵空樹t
輸出 - 選定邊的樹t
Begin create set for each vertices in graph g for each set of vertex u do add u in the vertexSet[u] done sort the edge list. count := 0 while count <= V – 1 do //as tree must have V – 1 edges ed := edgeList[count] //take an edge from edge list if the starting vertex and ending vertex of ed are in same set then merge vertexSet[start] and vertexSet[end] add the ed into tree t count := count + 1 done End
示例
#include<iostream>
#define V 7
#define INF 999
using namespace std;
//Cost matrix of the graph
int costMat[V][V] = {
{0, 1, 3, 4, INF, 5, INF},
{1, 0, INF, 7, 2, INF, INF},
{3, INF, 0, INF, 8, INF, INF},
{4, 7, INF, 0, INF, INF, INF},
{INF, 2, 8, INF, 0, 2, 4},
{5, INF, INF, INF, 2, 0, 3},
{INF, INF, INF, INF, 4, 3, 0}
};
typedef struct{
int u, v, cost;
}edge;
void swapping(edge &e1, edge &e2){
edge temp;
temp = e1;
e1 = e2;
e2 = temp;
}
class Tree{
int n;
edge edges[V-1]; //as a tree has vertex-1 edges
public:
Tree(){
n = 0;
}
void addEdge(edge e){
edges[n] = e; //add edge e into the tree
n++;
}
void printEdges(){ //print edge, cost and total cost
int tCost = 0;
for(int i = 0; i<n; i++){
cout << "Edge: " << char(edges[i].u+'A') << "--" << char(edges[i].v+'A');
cout << " And Cost: " << edges[i].cost << endl;
tCost += edges[i].cost;
}
cout << "Total Cost: " << tCost << endl;
}
};
class VSet{
int n;
int set[V];//a set can hold maximum V vertices
public:
VSet(){
n = -1;
}
void addVertex(int vert){
set[++n] = vert; //add vertex to the set
}
int deleteVertex(){
return set[n--];
}
friend int findVertex(VSet *vertSetArr, int vert);
friend void merge(VSet &set1, VSet &set2);
};
void merge(VSet &set1, VSet &set2){
//merge two vertex sets together
while(set2.n >= 0)
set1.addVertex(set2.deleteVertex());
//addToSet(vSet1, delFromSet(vSet2));
}
int findVertex(VSet *vertSetArr, int vert){
//find the vertex in different vertex sets
for(int i = 0; i<V; i++)
for(int j = 0; j<=vertSetArr[i].n; j++)
if(vert == vertSetArr[i].set[j])
return i;//node found in i-th vertex set
}
int findEdge(edge *edgeList){
//find the edges from the cost matrix of Graph and store to edgeList
int count = -1, i, j;
for(i = 0; i<V; i++)
for(j = 0; j<i; j++)
if(costMat[i][j] != INF){
count++;
//fill edge list for the position 'count'
edgeList[count].u = i; edgeList[count].v = j;
edgeList[count].cost = costMat[i][j];
}
return count+1;
}
void sortEdge(edge *edgeList, int n){
//sort the edges of graph in ascending order of cost
int flag = 1, i, j;
for(i = 0; i<(n-1) && flag; i++){//modified bubble sort is used
flag = 0;
for(j = 0; j<(n-i-1); j++)
if(edgeList[j].cost > edgeList[j+1].cost){
swapping(edgeList[j], edgeList[j+1]);
flag = 1;
}
}
}
void kruskal(Tree &tr){
int ecount, maxEdge = V*(V-1)/2; //max n(n-1)/2 edges can have in a graph
edge edgeList[maxEdge], ed;
int uloc, vloc;
VSet VSetArray[V];
ecount = findEdge(edgeList);
for(int i = 0; i < V; i++)
VSetArray[i].addVertex(i);//each set contains one element
sortEdge(edgeList, ecount); //ecount number of edges in the graph
int count = 0;
while(count <= V-1){
ed = edgeList[count];
uloc = findVertex(VSetArray, ed.u);
vloc = findVertex(VSetArray, ed.v);
if(uloc != vloc){ //check whether source abd dest is in same set or not
merge(VSetArray[uloc], VSetArray[vloc]);
tr.addEdge(ed);
}
count++;
}
}
int main(){
Tree tr;
kruskal(tr);
tr.printEdges();
}輸出
Edge: B--A And Cost: 1 Edge: E--B And Cost: 2 Edge: F--E And Cost: 2 Edge: C--A And Cost: 3 Edge: G--F And Cost: 3 Edge: D--A And Cost: 4 Total Cost: 15
更新時間：2020 年 6 月 11 日
1K+ 瀏覽
廣告