【1】克鲁斯卡尔算法
普里姆算法是以某顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树。
克鲁斯卡尔算法是直接以边为目标去构建。
因为权值是在边上,直接去找最小权值的边来构建生成树也是很自然的想法,只不过构建时要考虑是否会形成环路而已。
此时我们用到了图的存储结构中的边集数组结构。
以下是边集数组结构的定义代码:
本算法所用同普里姆算法的实例,我们直接创建图的边集数组。
并对边的权值从小到大排序后如下图:
【2】克鲁斯卡尔算法及详解
克鲁斯卡尔算法及其详解:
鉴于此算法很简单,当 i=0, i=1, i=2时执行结果可以眼观,不再赘述。直接分析重点:
此算法的Find函数由边数e决定,时间复杂度为O(loge),而外面有一个for循环e次。
所以克鲁斯卡尔算法的时间复杂度为O(eloge)
对比两个算法:
克鲁斯卡尔算法主要针对边展开,边数少时效率会很高,所以对于稀疏图有优势
而普利姆算法对于稠密图,即边数非常多的情况会好些。
【3】克鲁斯卡尔算法实现
实现代码如下:
1 #include <iostream> 2 using namespace std; 3 4 #define MAXVER 9 5 #define MAXEDGE 15 6 7 typedef struct Node 8 { 9 int begin; // 起点 10 int weight; // 权值 11 int end; // 末点 12 } edgeNode; 13 14 class Graph 15 { 16 private: 17 edgeNode edge[MAXEDGE]; 18 public: 19 Graph() 20 { 21 for (int i = 0; i < MAXEDGE; ++i) 22 { 23 edge[i].begin = edge[i].weight = edge[i].end = 0; 24 } 25 } 26 ~Graph() 27 {} 28 29 public: 30 void InsertSort() 31 { 32 for (int i = 0; i < MAXEDGE- 1; ++i) 33 { 34 if (edge[i+1].weight < edge[i].weight) 35 { 36 Node temp = edge[i+1]; 37 int j = i + 1; 38 do 39 { 40 edge[j] = edge[j-1]; 41 --j; 42 } while(j >= 0 && edge[j].weight > temp.weight); 43 44 edge[j+1] = temp; 45 } 46 } 47 } 48 49 istream & operator>>(istream &in) 50 { 51 int begin, value, end; 52 cout << "请输入15条边的起点 终点 权值:" << endl; 53 for (int i = 0; i < MAXEDGE; ++i) 54 { 55 in >> begin >> end >> value; 56 edge[i].begin = begin; 57 edge[i].weight = value; 58 edge[i].end = end; 59 } 60 return in; 61 } 62 ostream & operator<<(ostream &out) 63 { 64 // 插入排序 65 InsertSort(); 66 out << "输出排序边权值后信息:" << endl; 67 for (int i = 0; i < MAXEDGE; ++i) 68 { 69 out << "edge[" << i << "] " << edge[i].begin << " " << edge[i].weight << " " << edge[i].end << endl; 70 } 71 return out; 72 } 73 // 克鲁斯卡尔算法 74 void MiniSpanTree_Kruskal() 75 { 76 int i = 0, n = 0, m = 0; 77 int parent[MAXVER]; 78 for ( ; i < MAXVER; ++i) 79 parent[i] = 0; 80 for (i = 0; i < MAXEDGE; ++i) 81 { 82 n = Find(parent, edge[i].begin); 83 m = Find(parent, edge[i].end); 84 if (n != m) 85 { 86 parent[n] = m; 87 cout << " " << edge[i].begin << " " << edge[i].end << " " << edge[i].weight << endl; 88 } 89 } 90 } 91 92 int Find(int *parent, int f) 93 { 94 while (parent[f] > 0) 95 f = parent[f]; 96 return f; 97 } 98 }; 99 100 istream & operator>>(istream &in, Graph &g) 101 { 102 g >> in; 103 return in; 104 } 105 106 ostream & operator<<(ostream &out, Graph &g) 107 { 108 g << out; 109 return out; 110 } 111 112 void main() 113 { 114 Graph myg; 115 cin >> myg; 116 cout << myg; 117 myg.MiniSpanTree_Kruskal(); 118 } 119 // 备注: 120 // 最小生成树克鲁斯卡尔算法实现 121 // 整理于2013-12-04 122 // 测试需要输入: 123 /* 124 起始 终点 权值 125 0 1 10 126 0 5 11 127 1 2 18 128 1 8 12 129 1 6 16 130 2 8 8 131 2 3 22 132 3 8 21 133 3 6 24 134 3 7 16 135 3 4 20 136 4 7 7 137 4 5 26 138 5 6 17 139 6 7 19 140 */
Good Good Study, Day Day Up.
顺序 选择 循环 总结