【大话数据结构C语言】46 最小生成树（克鲁斯卡尔算法）

欢迎关注我的公众号是【CodeAllen】，关注回复【1024】获取资源
程序员技术交流①群：736386324 ，程序员技术交流②群：371394777    

无论是普里姆算法（Prim）还是克鲁斯卡尔算法（Kruskal），他们考虑问题的出发点都是：为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能的小。 

普里姆算法是以某顶点为起点，逐步找各个顶点上最小权值的边来构建最小生成树的

kruskal.c

  

   

    

     

    
    

     

      int Find(int *parent, int f)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    while( parent[f] > 0 )
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              f = parent[f];
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     
    return f;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      // Kruskal算法生成最小生成树
     
    
   

    

     

    
    

     

      void MiniSpanTree_Kruskal(MGraph G)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int i, n, m;
     
    
   

    

     

    
    

     

          Edge edges[MAGEDGE];    // 定义边集数组
     
    
   

    

     

    
    

     
    int parent[MAXVEX];     // 定义parent数组用来判断边与边是否形成环路
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     
    for( i=0; i < G.numVertexes; i++ )
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              parent[i] = 0;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     
    for( i=0; i < G.numEdges; i++ )
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              n = Find(parent, edges[i].begin);   // 4 2 0 1 5 3 8 6 6 6 7
     
    
   

    

     

    
    

     

              m = Find(parent, edges[i].end);     // 7 8 1 5 8 7 6 6 6 7 7
     
    
   

    

     

    
    

     
        
     
    
   

    

     

    
    

     
        if( n != m )        // 如果n==m，则形成环路，不满足！
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  parent[n] = m;  // 将此边的结尾顶点放入下标为起点的parent数组中，表示此顶点已经在生成树集合中
     
    
   

    

     

    
    

     
            printf("(%d, %d) %d ", edges[i].begin, edges[i].end, edges[i].weight);
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: allen5g.blog.csdn.net，作者：CodeAllen的博客，版权归原作者所有，如需转载，请联系作者。

原文链接：allen5g.blog.csdn.net/article/details/116808761