有一个连通图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
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; //图的成本矩阵 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: 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