Kruskal 算法是一个求最小生成树的算法，即求最小的开销等

 算法可以这样，要求得最小生成树，那么n个节点只能包括n-1条边

 所以我们应该转换为寻找这最短的n-1条边，因此，可以先对所有的

 边进行从小到大排序，每次取出一条边来进行试探，看是否够成环，

 如果不构成环，那么肯定是最短的路径了，因为每次都是取最小

 的边来试探，最终可以求得最小的生成树代价和。

 

/*	Filename:kruskal.cpp	Author: xiaobing	E-mail: xiaobingzhang29@gmail.com	Date: 2013-08-31*/#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define N 100#define INF 1000000using namespace std;/* Kruskal 算法是一个求最小生成树的算法，即求最小的开销等 算法可以这样，要求得最小生成树，那么n个节点只能包括n-1条边 所以我们应该转换为寻找这最短的n-1条边，因此，可以先对所有的 边进行从小到大排序，每次取出一条边来进行试探，看是否够成环， 如果不构成环，那么肯定是最短的路径了，因为每次都是取最小 的边来试探，最终可以求得最小的生成树代价和。 用到的数据结构： struct edge 表示一条边，包括两个端点及其代价 edge graph[N] 表示有N条边组成的图 int father[N] 表示每个点的最上层的根节点 解释：因为这里需要判断是否形成环路，可以这样，每添加一条 边，看两个点是否在已经添加进去的边的点集中，若对需要添加 的这条边，发现两个点都在之前的那个集合中，这一定会形成回 路，所以，这里设置一个数组father[N],起初时，每个值为-1,代 表每个点的根节点都没有(因为没有添加一条边进去)，当添加一条 边后，如果他们的根节点不同，则设置大的那个点的父节点为小 的那个点，如x > y 则 father[x] = y,这样每个点都只有一个根， 或者没有根，为-1,所以对添加进的节点，都可以查出他的根，然后 做比较，都相同，说明已位于添加进的节点中了，否则把该边添加 进去。 *///定义一条边struct edge{ int u; //起始点 int v; //目的点 int cost; //两点之间的代价};//这是一个对块数排序算法调用的一个比较函数bool cmp(const edge &a, const edge &b){ return a.cost < b.cost;}//查找一个节点的根节点int findFather(int father[], int x){ //如果他的父节点不为-1,则应该递归，直到找到其父节点 if(father[x] != -1){ //将沿途的所有节点都指向同一个根节点 return father[x] = findFather(father, father[x]); } //若为-1,则该点就是根 return x;}//添加一条边bool unionEdge(int father[], int x, int y){ //找到一条边的两个端点的根节点 x = findFather(father, x); y = findFather(father, y); //根节点相同，说明已经加入了，再加入该边 //则会形成回路，该边舍弃，返回fasle if(x == y){ return false; } //若不同，让大的节点的根节点指向小的节点 if(x > y) father[x] = y; if(x < y) father[y] = x; //该边可以加入，返回true return true;}int main(){ edge graph[N]; //定义了一个包含N条边的图 int father[N]; //定义了一个包含N个节点的根节点 int i,j, n; //n代表节点数 cin>>n; //初始化数组 memset(graph, 0, sizeof(graph)); //初始化为-1表示任何点都没有父节点，即没有一条边已加入 memset(father, -1, sizeof(father)); int k = 0, cost, temp; //接收数据 for(i = 0;i < n;i++) for(j = 0;j < n;j++){ if(i > j){ graph[k].u = i; graph[k].v = j; cin>>cost; //对于小于0的值，表示不可达，所以代价为无穷大INF if(cost < 0){ graph[k].cost = INF; } else { graph[k].cost = cost; } k++; continue; } //由于是对称的，该值无用，但得接收 cin>>temp; } //将所有边从小到大排序 sort(graph, graph + k, cmp); //打印排序后的边 for(i = 0;i < k;i++){ cout<
            <<" "<
             
              <<"->"<
              
               <<": "<
               
                <
               
              
             
           
          
         
        
       
      
     
    

测试例子：

 

 

70 5 -1 -1 -1 11 25 0 10 8 -1 -1 13-1 10 0 7 -1 -1 -1-1 8 7 0 12 9 4-1 -1 -1 12 0 10 -111 -1 -1 9 10 0 32 13 -1 4 -1 3 0

结果：

 

 

0 6->0: 21 6->5: 32 6->3: 43 1->0: 54 3->2: 75 3->1: 86 5->3: 97 2->1: 108 5->4: 109 5->0: 1110 4->3: 1211 6->1: 1312 2->0: 100000013 6->4: 100000014 6->2: 100000015 3->0: 100000016 5->2: 100000017 5->1: 100000018 4->2: 100000019 4->1: 100000020 4->0: 1000000最小生成树代价和sum : 31