最小生成树—kruskal算法和prim算法
主要讲解求解最小生成树的两种不同的贪心策略，最小生成树的概念就不讲解了，下面直接给出两种算法的理解。
kruskal算法：是贪婪策略，连续地按照最小的权选择边，并且当所选的边不产生环时就把它作为取定的边。或者这样理解，开始把所有结点都看成树，这样所有的树在一起看作一个森林，每次选择权值最小的边，该边连接不同的树，当把该边的两棵树合并成一颗树。例如下图中的例子
红色表示两个结点合并成一棵树，选择图中最小权值的边3，改边两端的结点属于不同的树，则把改边作为取定边，把C结点的树合并到A结点所属的树。即由图1变为图2，由于图2只有一棵树，完成最小树生成树。
图1 图2
在编程中通过结点的flag标记该结点属于哪棵树，开始时所有结点的flag大于零，若其所在边被选择为最小生成树的边，则把该结点的flag标记为相应的负数。下面结合图讲解：
其中红色边表示该边的两端结点在同一棵树中，h、g、f结点在同一棵树中，则h、g、f 结点的标示符flag都为-1；c、i结点在同一棵树中且不是与h、g、f在同一棵树中，则c、i结点的标示符flag为-2；其他结点的flag为大于零的整数。当选择图中的最小边时，若边的两端结点的flag标志为负值且相等，则表示该边在最小生成树中了，可以排除不会再被选中，如图中的：权值为1、2、2的三个边。那么权值最小的边为4有三个，可以先选择其中的任意一个：
1.若选择边的两端结点为a、b，首先判断a、b结点中的标示符flag都为正，表示a、b两点在不同的树中并且树中只有自己。将两个树合并，即a、b结点标示符flag为-3
2. 选择权值最小的边，有两个未被选的边权值为4(因为边的端结点为a、b，两个端点的flag值为负且相等，表明该边已被选为最小生成树的边)，此次选择到端点为e、f 的边。由于f的标示符flag为负值，表明f和其他结点组成一棵树，e的结点为正，表明其单独构成一棵树，直接把e结点构成的树合并到 f 结点所在的树中(把f 结点的flag赋值给e结点的flag，便可完成树的合并）
3. 选择权值最小的边，只有一个未被选的权值为4的边，端结点为c、f。c、f 的标示符flag都为负且不相等，一个为-2一个为-1。表明c和其他结点组成一棵树，f 和其他结点组成一棵树，并且是不同的两棵树。那么要把这两棵树合并，做法：把c所在的树中所有结点的flag 赋值为f 的标示符flag的值(即把c所在树中的结点c、i的flag赋值为-1)，这样便完成两棵树的合并。
一直合并，知道所有的结点都在同一棵树中，即所有的结点的标示符flag都为负值且相等。
Prim算法：从任意的结点r开始，构成一棵树，选择该树中结点所在的边的权值最小的一个边并且该边的另一个结点不在这课树中，一直增长直到覆盖所有的结点。
如上图中，在a、b、c、i 结点组成的树中，选择与该树连接的最小权值的边，即在(a,h)、(b,h)、(i,h）、(i,g)、(c,f)、(c,d)的边中选择权值最小的边，如图中为(c,f)的边权值为4，则把该边加入到最小生成树中。注意：所选则的边的两个结点不能同时在树中。
在编程中，采用结点的标示符flag来判断某节点是否在树中，树中的结点的flag值都为-1，其他结点为正的。
Minspantree.h
#pragma once#include<iostream>#include<string>#include<vector>using namespace std;template<typename Comparable>struct Node //图中的结点E{Comparable element;//结点的元素vector<Node<Comparable>*> next; //结点的连接指针,指向多个结点vector<Node<Comparable>*> father; //父亲结点int flag; //主要用于Kruskal算法标记该结点属于那一棵树Node(Comparable e,int f):element(e),flag(f){}};template<typename Comparable>struct Edge //图中边{Node<Comparable>* N1; //结点1Node<Comparable>* N2; //结点2int weight; //两个结点间的权值Edge(Node<Comparable>* n1,Node<Comparable>* n2,int w):N1(n1),N2(n2),weight(w){}};template<typename Comparable>class graph{public:void insert(Comparable *a,int *matrix,int *w,int n);//a:图中个结点的元素；matrix:邻接矩阵 //w为相连结点间的权值，n结点数void Kruskal();void Prim();private:vector<Node<Comparable>*> root; //存储每个结点的地址vector<Edge<Comparable>*> side; //存储每条边的地址vector<Edge<Comparable>*> Mintree;//保存最小生成树的边bool find(Edge<Comparable>* edge,int f);//Kruskal,判断某边的两端结点是否在一颗树中void changef(Node<Comparable>* t,int f);//Kruskal,将结点合并，}; //即把结点中的标示flag改为相等的数值，表示在同一棵树中
Minspantree.cpp
#include "stdafx.h"#include"Minspantree.h"#include<iostream>#include<string>#include<vector>using namespace std;template<typename Comparable>void graph<Comparable>::insert(Comparable *a,int *matrix,int *w,int n)//实现图的构建，包括结点和边{for(int i=0;i<n;i++){Node<Comparable>* node=new Node<Comparable>(a[i],i+1);root.push_back(node);}Node<Comparable>* node=NULL;Node<Comparable>* temp=NULL;int k=0;for(int i=0;i<n;i++){node=root[i];for(int j=0;j<n;j++){if(matrix[n*i+j]!=0){temp=root[j];node->next.push_back(temp);temp->father.push_back(node);if(j>i){Edge<Comparable>* edge=new Edge<Comparable>(node,temp,w[k]);k=k+1;side.push_back(edge);}}}}}template<typename Comparable>void graph<Comparable>::Kruskal() //Kruskal算法实现最小生成树{ //其中结点中的flag标示一个边的两端结点是否在同一棵树中int en=side.size(); //图中总共有多少条边Edge<Comparable>* edge=NULL;for(int i=0;i<en;i++) //排序，按边权重升序排序。注：此处可以采用快排可减少排序的时间{for(int j=i;j<en;j++)if(side[i]->weight>side[j]->weight){edge=side[i];side[i]=side[j];side[j]=edge;}}int f=-1;edge=side[0]; //将权值最小的边放入到树中Mintree.push_back(edge);edge->N1->flag=f;edge->N2->flag=f; //将edge两端结点的标志flag设置为同一个数，表明两个结点在同一颗树中for(int i=1;i<en;i++) {edge=side[i];f=f-1;if(find(edge,f)) //如果edge两个结点不是同时在同一颗树中，则连接该条边Mintree.push_back(edge);}cout<<"Kruskal算法最小生成树:"<<endl;int n=Mintree.size();int sum=0;for(int i=0;i<n;i++){edge=Mintree[i];cout<<"("<<edge->N1->element<<","<<edge->N2->element<<","<<edge->weight<<")"<<" ";sum+=edge->weight;}cout<<endl;cout<<"最小权值:"<<sum<<endl;}template<typename Comparable>bool graph<Comparable>::find(Edge<Comparable>* edge,int f){if(edge->N1->flag>0&&edge->N2->flag>0){edge->N1->flag=f;edge->N2->flag=f;return true;}else if(edge->N1->flag>0&&edge->N2->flag<0){edge->N1->flag=edge->N2->flag;return true;}else if(edge->N1->flag<0&&edge->N2->flag>0){edge->N2->flag=edge->N1->flag;return true;}else if(edge->N1->flag<0&&edge->N2->flag<0&&edge->N1->flag!=edge->N2->flag){changef(edge->N2,edge->N1->flag);return true;}elsereturn false;}template<typename Comparable> void graph<Comparable>::changef(Node<Comparable>* t,int f){int n=Mintree.size();int flag=t->flag;Node<Comparable>* n1=NULL;Node<Comparable>* n2=NULL;Edge<Comparable>* edge=NULL;for(int i=0;i<n;i++){edge=Mintree[i];n1=edge->N1;n2=edge->N2;if(n1->flag==flag)n1->flag=f;if(n2->flag==flag)n2->flag=f;}t->flag=f;}template<typename Comparable> void graph<Comparable>::Prim() //Prim算法实现最小生成树{Node<Comparable>* node=NULL;Edge<Comparable>* edge=NULL;Edge<Comparable>* result=new Edge<Comparable>(NULL,NULL,1000);Edge<Comparable>* temp=new Edge<Comparable>(NULL,NULL,1000);int en=side.size();int n=root.size();node=root[0];node->flag=-1; //初始化一个根结点int k=0;while(k<n-1){for(int i=0;i<en;i++){edge=side[i];if(edge->N1->flag*edge->N2->flag<0&&edge->weight<result->weight){result=edge;}}if(result->N1->flag<0)result->N2->flag=result->N1->flag;elseresult->N1->flag=result->N2->flag;Mintree.push_back(result);result=temp;k=k+1;}cout<<"prim算法最小生成树:"<<endl; n=Mintree.size();int sum=0;for(int i=0;i<n;i++){edge=Mintree[i];cout<<"("<<edge->N1->element<<","<<edge->N2->element<<","<<edge->weight<<")"<<" ";sum+=edge->weight;}cout<<endl;cout<<"最小权值:"<<sum<<endl;}
Algorithm-graph2.cpp
// Algorithm-graph2.cpp : 定义控制台应用程序的入口点。//主要是实现最小生成树#include "stdafx.h"#include"Minspantree.h"#include"Minspantree.cpp"#include<string>#include<iostream>using namespace std;int _tmain(int argc, _TCHAR* argv[]){graph<string> g;int n=9;int matrix[81]={0,1,0,0,0,0,0,1,0, 1,0,1,0,0,0,0,1,0,0,1,0,1,0,1,0,0,1,0,0,1,0,1,1,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,1,1,0,1,0,0,0,0,0,0,0,1,0,1,1,1,1,0,0,0,0,1,0,1,0,0,1,0,0,0,1,1,0};string a[9]={"a","b","c","d","e","f","g","h","i"};int w[14]={4,8,8,11,7,4,2,9,14,10,2,1,6,7};g.insert(a,matrix,w,n);g.Kruskal();g.Prim();return 0;}