首页 > 代码库 > Geeks : Kruskal’s Minimum Spanning Tree Algorithm 最小生成树
Geeks : Kruskal’s Minimum Spanning Tree Algorithm 最小生成树
寻找图中最小连通的路径,图如下:
算法步骤:
1. Sort all the edges in non-decreasing order of their weight. 2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. 3. Repeat step#2 until there are (V-1) edges in the spanning tree.关键是第二步难,这里使用Union Find来解决,可以几乎小于O(lgn)的时间效率来判断是否需要判断的顶点和已经选择的顶点成环。
正因为这步,使得原本简单的贪心法,变得不那么简单了。
这样本算法的时间效率达到:max(O(ElogE) , O(ElogV))
原文参考:http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/
#pragma once #include <stdio.h> #include <stdlib.h> #include <string.h> class KruskalsMST { struct Edge { int src, des, weight; }; static int cmp(const void *a, const void *b) { Edge *a1 = (Edge *) a, *b1 = (Edge *) b; return a1->weight - b1->weight; } struct Graph { int V, E; Edge *edges; Graph(int v, int e) : V(v), E(e) { edges = new Edge[e]; } virtual ~Graph() { if (edges) delete [] edges; } }; struct SubSet { int parent, rank; }; int find(SubSet *subs, int i) { if (subs[i].parent != i) subs[i].parent = find(subs, subs[i].parent); return subs[i].parent; } void UnionTwo(SubSet *subs, int x, int y) { int xroot = find(subs, x); int yroot = find(subs, y); if (subs[xroot].rank < subs[yroot].rank) subs[xroot].parent = yroot; else if (subs[xroot].rank > subs[yroot].rank) subs[yroot].parent = xroot; else { subs[xroot].rank++; subs[yroot].parent = xroot; } } Graph *graph; Edge *res; SubSet *subs; void initSubSet() { subs = new SubSet[graph->V]; for (int i = 0; i < graph->V; i++) { subs[i].parent = i; subs[i].rank = 0; } } void mst() { res = new Edge[graph->V-1]; qsort(graph->edges, graph->E, sizeof(graph->edges[0]), cmp); initSubSet(); for (int e = 0, i = 0; e < graph->V - 1 && i < graph->E; i++) { Edge nextEdge = graph->edges[i]; int x = find(subs, nextEdge.src); int y = find(subs, nextEdge.des); if (x != y) { res[e++] = nextEdge; UnionTwo(subs, x, y); } } } void printResult() { printf("Following are the edges in the constructed MST\n"); for (int i = 0; i < graph->V-1; ++i) printf("%d -- %d == %d\n", res[i].src, res[i].des, res[i].weight); } public: KruskalsMST() { /* Let us create following weighted graph 10 0--------1 | \ | 6| 5\ |15 | \ | 2--------3 4 */ int V = 4; // Number of vertices in graph int E = 5; // Number of edges in graph graph = new Graph(V, E); // add edge 0-1 graph->edges[0].src = http://www.mamicode.com/0;>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。