【贪心法求解最小生成树之Kruskal算法详细分析】---Greedy Algorithmfor MST
初衷：
最近在看算法相关的东西，看到贪心法解决mst的问题，可惜树上讲解的不是很清新，到网上找了很多资料讲解的也不透彻
只是随便带过就草草了事、这几天抽空看了下，总算基本思路理清楚了
主要还是得感谢强大的google，帮我找到一个很好的英文资料。（下面有链接，有兴趣的同学可以看看）
理顺了思路，就和大家分享下~希望对学习贪心法的同学会有所帮助。
这篇博客的主要内容是贪心法求解Minimum Spanning Tree (MST)（最小生成树）的问题
贪心法求解最小生成树常用的有两种算法，分别是PRim’s MST algorithm和Kruskal's MST algorithm(prim算法和kruskal算法)
这里主要说的是kruskal算法
最小生成树的简单定义：
给定一股无向联通带权图G(V,E).E中的每一条边(v,w)权值位C(v,w)。如果G的子图G'是一个包含G中所有定点的子图，那么G'称为G的生成树，如果G'的边的权值最小
那么G'称为G的最小生成树。
kruskal算法的基本思想：
1.首先将G的n个顶点看成n个孤立的连通分支（n个孤立点）并将所有的边按权从小大排序。
2.按照边权值递增顺序，如果加入边后存在圈则这条边不加，直到形成连通图
对2的解释：如果加入边的两个端点位于不同的连通支，那么这条边可以顺利加入而不会形成圈
本例中用到的图：
权值递增排序：
kruskal加边后情况：
所以对于任意边(u,v)要判断这两个点是不是存在于同一个连通支里。
如果是，则舍弃这条边，接着判断另一条边
如果不是，则把这条边加入到图中，并且把u，v属于的连通支合并
然后操作下一条边
这个算法执行的过程就是按照规定一个个连通支合并的过程，使最后只剩一个连通支。
What kind of data structure supportssuch Operations?
这是一个值得思考的问题、、、逛社区的时候，有用链表的、二维数组的、、这里不讨论这些存储结构的可行性
这里要讨论的是有向树的存储
some implementation details（基本操作）
makeset(x): create a singleton setcontaining just x //初始化的时候把整个图分为n个独立连通块
find(x): to which set does x belong? //对于任意给定点x，判断x属于哪一个连通块
union(x, y): merge the sets containing xand y //合并两个连通块其中，x，y为某边的两个端点，如果通过上面的find操作属于不同的连通块才把他们合并
Algorithm（算法实现）：
Kruskal(G)
1.For all u∈V do
makeset(u); //初始化，让每个点成为独立的连通块
2. X={Æ};
3. Sort the edges E by weight; //按边的权值大小排序
4. For all edges (u, v)∈ E in increasingorder of weight do //对于条边e(u,v)（权值递增顺序）判断能否加入到图中
iffind(u) ≠find(v) then //如两个端点不在同一个连通块，则合并这两个连通块
add edge (u, v) to X;
union(u, v);
下面是算法中的实现细节
How to store a set?（如何存储连通块）
例子;
{B, E}
{A, C, D, F, G, H}
对于每一个联通块，还有两个需要保存的，也就是树的根节点rank和树高height
Root: its parent pointer points toitself.
Rank: the height of subtree hanging fromthat node.
还有一个会用到的关系，对于树中的点x，p(x)表示x的父节点
下面是函数实现
Makeset(x)
1.P(x)=x; //Constant time operation
2.Rank(x)=0;
Find(x)
1.While x ≠P(x) do //The time taken is proportional to the height of the tree.
x=P(x);
2. return(x);
执行上述操作后的实例：
After makeset(A), makeset(B), …,makeset(G).（执行makeset后）
每个点成为了孤立的连通支，右上角的数字代表树的rank
After union(A,D), union(B,E), union(C,F).（合并AD，BE，CF后）
After union(C,G), union(E,A).（合并CG，EA后）
注意看新的连通支右上角的rank有变化，合并的过程中尽量使得rank达到最小
After union(B,G).
关于Rank的几点说明：
Property 1: For any x, rank(x) <rank(P(x)). 对于任意x，x的rank小于他的父节点的rank
Property 2: Any root node of rank k hasat least 2k nodes in its tree. 任何rank为k 的连通支至少有2k个节点
Property 3: If there are n elementsoverall, there can be at most n/2k nodes of rank k. 如果一共有n个节点，那么rank为k的连通支一共有n/2k个
对property2的解释：因为union的原则是让union后的树rank最小，所以union后的树至少是二叉树，也就是说除叶子节点外的节点至少有两个孩子。
对property3的解释：因为rank为k的树至少有2k 个节点，所以最多有n/2k个
算法效率分析：
Kruskal(G)
1.For all u∈V do
makeset(u); //初始化，让每个点成为独立的连通块
2. X={Æ};
3. Sort the edges E by weight; //按边的权值大小排序
4. For all edges (u, v)∈ E in increasingorder of weight do //对于条边e(u,v)（权值递增顺序）判断能否加入到图中
iffind(u) ≠find(v) then //如两个端点不在同一个连通块，则合并这两个连通块
add edge (u, v) to X;
union(u, v);
上面的算法中
makeset():可以在常数时间内完成
sort edges :对边的权值进行排序的效率O(|E|log|V|) （排序算法的时间效率、自己google不啰嗦）
find():由给定的点往上查找，直到树根为止所花时间为树的高度即log|V|。
注意：如何确定find()执行的次数是一个值得考虑的问题
如果从点的角度，是很难得到准确答案的，因为每个对于某一个点，和他相连的点是不确定的，即不通过的点情况不同，要逐一考虑岂不很麻烦
其实find()执行的次数是和边数紧密相连的。请看算法中，循环的体是依据边的权值顺序展开的。而对于每一条我们考虑的边，都要考虑它连接的两个点
所以，find()的执行次数就是边数的两倍。执行一个finad()的效率是log|V|，而union基本可在常数时间内完成
所以
Union and Find operations: O(|E|log|V|)
其实这个算法的思想很简单、每一次选最小的，如果符合条件就把它加入到我们的结果中，如果不满足条件，则选下一个最小的
只是实现起来考虑的需要多一些、比如用何种数据结构存储、判断两个点是不是属于同一个连通支等等
可见，贪心法只是提供一种解决的基本思路，要真正解决问题还要考虑如何实现、这也是很关键的一点。
如果你看到这里，可能会发现这个算法的效率不是很可观、在最后的union and find中所用的时间和点的数量n有很大的关系。
如果n很大的话，就会花很多时间。
那么、这个算法的效率可以提高吗？
答案是肯定的。用到的技术为
Amortized Analysis 平摊分析（也叫摊销分析），这可以说是一种很神奇的思想，先透露一下吧
对于这个问题的union and find操作，本文中的效率为O(|E|log|V|)。Amortized Analysis后，可以让复杂度为：O(|E|Log*n)
Log*n是个什么东西呢？当n为宇宙中所有物质的数量的时候，Log*n<=8
也就是让上文中的log(n)的最大值降到8.
如何？是不是很客观的效率提升。。。。
在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。
例如，对于如上图G4所示的连通网可以有多棵权值总和不相同的生成树。
克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。
基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。 具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。
以上图G4为例，来对克鲁斯卡尔进行演示(假设，用数组R保存最小生成树结果)。
第1步：将边<E,F>加入R中。 边<E,F>的权值最小，因此将它加入到最小生成树结果R中。 第2步：将边<C,D>加入R中。 上一步操作之后，边<C,D>的权值最小，因此将它加入到最小生成树结果R中。 第3步：将边<D,E>加入R中。 上一步操作之后，边<D,E>的权值最小，因此将它加入到最小生成树结果R中。 第4步：将边<B,F>加入R中。 上一步操作之后，边<C,E>的权值最小，但<C,E>会和已有的边构成回路；因此，跳过边<C,E>。同理，跳过边<C,F>。将边<B,F>加入到最小生成树结果R中。 第5步：将边<E,G>加入R中。 上一步操作之后，边<E,G>的权值最小，因此将它加入到最小生成树结果R中。 第6步：将边<A,B>加入R中。 上一步操作之后，边<F,G>的权值最小，但<F,G>会和已有的边构成回路；因此，跳过边<F,G>。同理，跳过边<B,C>。将边<A,B>加入到最小生成树结果R中。
此时，最小生成树构造完成！它包括的边依次是：<E,F><C,D> <D,E> <B,F> <E,G> <A,B>。
根据前面介绍的克鲁斯卡尔算法的基本思想和做法，我们能够了解到，克鲁斯卡尔算法重点需要解决的以下两个问题： 问题一 对图的所有边按照权值大小进行排序。 问题二 将边添加到最小生成树中时，怎么样判断是否形成了回路。
问题一很好解决，采用排序算法进行排序即可。
问题二，处理方式是：记录顶点在"最小生成树"中的终点，顶点的终点是"在最小生成树中与它连通的最大顶点"(关于这一点，后面会通过图片给出说明)。然后每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。 以下图来进行说明：
在将<E,F> <C,D> <D,E>加入到最小生成树R中之后，这几条边的顶点就都有了终点：
(01) C的终点是F。 (02) D的终点是F。 (03) E的终点是F。 (04) F的终点是F。
关于终点，就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是"与它连通的最大顶点"。 因此，接下来，虽然<C,E>是权值最小的边。但是C和E的重点都是F，即它们的终点相同，因此，将<C,E>加入最小生成树的话，会形成回路。这就是判断回路的方式。
有了前面的算法分析之后，下面我们来查看具体代码。这里选取"邻接矩阵"进行说明，对于"邻接表"实现的图在后面的源码中会给出相应的源码。
1. 基本定义
// 边的结构体class EData{ public: char start; // 边的起点 char end; // 边的终点 int weight; // 边的权重 public: EData(){} EData(char s, char e, int w):start(s),end(e),weight(w){}};EData是邻接矩阵边对应的结构体。
class MatrixUDG { #define MAX 100 #define INF (~(0x1<<31)) // 无穷大(即0X7FFFFFFF) private: char mVexs[MAX]; // 顶点集合 int mVexNum; // 顶点数 int mEdgNum; // 边数 int mMatrix[MAX][MAX]; // 邻接矩阵 public: // 创建图(自己输入数据) MatrixUDG(); // 创建图(用已提供的矩阵) //MatrixUDG(char vexs[], int vlen, char edges[][2], int elen); MatrixUDG(char vexs[], int vlen, int matrix[][9]); ~MatrixUDG(); // 深度优先搜索遍历图 void DFS(); // 广度优先搜索（类似于树的层次遍历） void BFS(); // prim最小生成树(从start开始生成最小生成树) void prim(int start); // 克鲁斯卡尔（Kruskal)最小生成树 void kruskal(); // 打印矩阵队列图 void print(); private: // 读取一个输入字符 char readChar(); // 返回ch在mMatrix矩阵中的位置 int getPosition(char ch); // 返回顶点v的第一个邻接顶点的索引，失败则返回-1 int firstVertex(int v); // 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1 int nextVertex(int v, int w); // 深度优先搜索遍历图的递归实现 void DFS(int i, int *visited); // 获取图中的边 EData* getEdges(); // 对边按照权值大小进行排序(由小到大) void sortEdges(EData* edges, int elen); // 获取i的终点 int getEnd(int vends[], int i);};MatrixUDG是邻接矩阵对应的结构体。 mVexs用于保存顶点，mVexNum是顶点数，mEdgNum是边数；mMatrix则是用于保存矩阵信息的二维数组。例如，mMatrix[i][j]=1，则表示"顶点i(即mVexs[i])"和"顶点j(即mVexs[j])"是邻接点；mMatrix[i][j]=0，则表示它们不是邻接点。
2. 克鲁斯卡尔算法
/* * 克鲁斯卡尔（Kruskal)最小生成树 */void MatrixUDG::kruskal(){ int i,m,n,p1,p2; int length; int index = 0; // rets数组的索引 int vends[MAX]={0}; // 用于保存"已有最小生成树"中每个顶点在该最小树中的终点。 EData rets[MAX]; // 结果数组，保存kruskal最小生成树的边 EData *edges; // 图对应的所有边 // 获取"图中所有的边" edges = getEdges(); // 将边按照"权"的大小进行排序(从小到大) sortEdges(edges, mEdgNum); for (i=0; i<mEdgNum; i++) { p1 = getPosition(edges[i].start); // 获取第i条边的"起点"的序号 p2 = getPosition(edges[i].end); // 获取第i条边的"终点"的序号 m = getEnd(vends, p1); // 获取p1在"已有的最小生成树"中的终点 n = getEnd(vends, p2); // 获取p2在"已有的最小生成树"中的终点 // 如果m!=n，意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路 if (m != n) { vends[m] = n; // 设置m在"已有的最小生成树"中的终点为n rets[index++] = edges[i]; // 保存结果 } } delete[] edges; // 统计并打印"kruskal最小生成树"的信息 length = 0; for (i = 0; i < index; i++) length += rets[i].weight; cout << "Kruskal=" << length << ": "; for (i = 0; i < index; i++) cout << "(" << rets[i].start << "," << rets[i].end << ") "; cout << endl;}
我们在前面讲过的《克里姆算法》是以某个顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树的。同样的思路，我们也可以直接就以边为目标去构建，因为权值为边上，直接找最小权值的边来构建生成树也是很自然的想法，只不过构建时要考虑是否会形成环而已，此时我们就用到了图的存储结构中的边集数组结构，如图7-6-7
假设现在我们已经通过邻接矩阵得到了边集数组edges并按权值从小到大排列如上图。
下面我们对着程序和每一步循环的图示来看：
算法代码：（改编自《大话数据结构》）
C++ Code
1234567891011121314151617181920212223242526272829303132333435363738394041424344
typedef struct{ int begin; int end; int weight;} Edge;/* 查找连线顶点的尾部下标 */int Find(int *parent, int f){ while (parent[f] > 0) f = parent[f]; return f;}/* 生成最小生成树 */void MiniSpanTree_Kruskal(MGraph G){ int i, j, n , m; int k = 0; int parent[MAXVEX];/* 定义一数组用来判断边与边是否形成环路 */ Edge edges[MAXEDGE];/* 定义边集数组,edge的结构为begin,end,weight,均为整型 */ /* 此处省略将邻接矩阵G转换为边集数组edges并按权由小到大排列的代码*/ for (i = 0; i < G.numVertexes; i++) parent[i] = 0; cout << "打印最小生成树：" << endl; for (i = 0; i < G.numEdges; i++)/* 循环每一条边 */ { n = Find(parent, edges[i].begin); m = Find(parent, edges[i].end); if (n != m)/* 假如n与m不等，说明此边没有与现有的生成树形成环路 */ { parent[n] = m;/* 将此边的结尾顶点放入下标为起点的parent中。 */ /* 表示此顶点已经在生成树集合中 */ cout << "(" << edges[i].begin << ", " << edges[i].end << ") " << edges[i].weight << endl; } }}
1、程序 第17～28行是初始化操作，中间省略了一些存储结构转换代码。
2、第30～42行，i = 0 第一次循环，n = Find( parent,4) = 4; 同理 m = 7; 因为 n != m 所以parent[4] = 7, 并且打印 “ (4, 7) 7 ” 。此时我们已经将边（v4, v7)纳入到最小生成树中，如下图的第一个小图。
3、继续循环，当i从1 至 6 时，分别把（v2, v8), (v0, v1),(v0, v5), (v1, v8), (v3, v7), (v1, v6)纳入到最小生成树中，如下图所示，此时parent数组为
{ 1, 5, 8, 7, 7, 8, 0, 0, 6 }，如何解读现在这些数字的意义呢？从图i = 6来看，其实是有两个连通的边集合A与B 纳入到最小生成树找中的，如图7-6-12所示。parent[0] = 1表示v0 和v1 已经在生成树的边集合A中，将parent[0] = 1中的 1 改成下标，由parent[1] = 5 ，表示v1 和v5 已经在生成树的边集合A中，parent[5] = 8 ，表示v5 和v8 已经在生成树的边集合A中，parent[8] = 6 ，表示v8 和v6 已经在生成树的边集合A中，parent[6] = 0 表示集合A暂时到头，此时边集合A有 v0, v1, v5, v6,v8。查看parent中没有查看的值，parent[2] = 8，表明v2 和 v8在一个集合中，即A中。再由parent[3] = 7, parent[4] = 7 和 parent[7] = 0 可知v3, v4, v7 在一个边集合B中。
4、当i = 7时， 调用Find函数，n = m = 6,不再打印，继续下一循环，即告诉我们，因为（v5, v6) 使得边集合A形成了回路，因此不能将其纳入生成树中，如图7-6-12所示。
5、当i = 8时与上面相同，由于边(v1, v2) 使得边集合A形成了回路，因此不能将其纳入到生成树中，如图7-6-12所示。
6、当i = 9时，n = 6, m = 7, 即parent[6] = 7，打印“（6， 7）19” ，此时parent数组为{ 1, 5, 8, 7, 7,8, 7, 0, 6 } ，如图7-6-13所示。
最后，我们来总结一下克鲁斯卡尔算法的定义：
假设 N = （V, {E} ）是连通网，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T { V, {} }，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将其加入到 T 中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。
此算法的Find函数由边数e决定，时间复杂度为O(loge)，而外面有一个for循环e次，所以克鲁斯卡尔算法的时间复杂度为O(eloge)。
对比普里姆和克鲁斯卡尔算法，克鲁斯卡尔算法主要针对边来展开，边数少时效率比较高，所以对于稀疏图有较大的优势；而普里姆算法对于稠密图，即边数非常多的情况下更好一些。
新闻热点
疑难解答
