Kruskal的最小生成树算法
有一个连通图G(V,E)并给出了每个边的权重或成本。Kruskal的算法将使用图形和成本找到最小生成树。
这是合并树方法。最初，有不同的树，此算法将采用成本最小的那些边合并它们，并形成一棵树。
在此问题中，所有边均根据其成本列出并排序。从列表中，取出成本最低的边并添加到树中，然后每一次检查是否形成边，如果形成一个循环，则从列表中丢弃边并移至下一条边。
该算法的时间复杂度为O（E log E）或O（E log V），其中E是许多边，V是许多顶点。
输入输出
Input:Adjacency matrixOutput:
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: Graph, t: Tree)
输入-给定图g和空树t
输出-具有选定边的树t
Begincreate 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;
//图的成本矩阵
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) {
//将两个顶点集合并在一起
while(set2.n >= 0)
set1.addVertex(set2.deleteVertex());
//addToSet（vSet1，delFromSet(vSet2)）;
}
int findVertex(VSet *vertSetArr, int vert) {
//在不同的顶点集中找到顶点
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) {
//从Graph的成本矩阵中找到边并存储到edgeList-
int count = -1, i, j;
for(i = 0; i<V; i++)
for(j = 0; j<i; j++)
if(costMat[i][j] != INF) {
count++;
//填充位置“计数”的边缘列表
edgeList[count].u = i; edgeList[count].v = j;
edgeList[count].cost = costMat[i][j];
}
return count+1;
}
void sortEdge(edge *edgeList, int n) {
//以成本的升序对图的边缘进行排序
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: 1Edge: 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的最小生成树算法 的全部内容， 来源链接： utcz.com/z/330787.html
