求最小生成树Kruskal算法

古城微笑少年丶 2022-08-21 04:19 173阅读 0赞

**求最小生成树Kruskal算法**

#  本文取自《数据结构与算法》(C语言版)(第三版)，出版社是清华大学出版社。 #

本博文作为学习资料整理。源代码是VC++ 6.0上可执行程序，我挪到了VS2010中执行。

在VS2010中新建C++ Win32 控制台应用程序项目，创建结果截图：

![Center][]

Kruskal算法的基本思想是：将图G中的边按权值从小到大的顺序依次添加，如果添加的边使生成树T构成回路，则将其舍弃，依此下去，直到T中包含的边数为n-1条边为止，此时的T即为最小生树。

Kruskal算法步骤图示例：

![SouthEast][]  
为了方便输出，将最小生成树的输入格式规定为以下形式：  
(顶点1, 顶点2): 权值1  
表示顶点1到顶点2有路径，路径上的权值为1.  
其程序如下：

#include "stdafx.h"
       #include<stdio.h>
       #include<stdlib.h>
       #include<string.h>
       #define MaxVertexNum 100
       //队列的声明
       typedef struct Qnode
       {
         int data;
         struct Qnode* next;
         struct Qnode* prev;
       }Qnode;
    
       typedef struct queue
       {
         Qnode* first;
         Qnode* tail;
       }Queue;
    
       int isQueueEmpty(Queue* pQue)
       {
         if(pQue->first==pQue->tail)
           return 1;
         else
           return 0;
       }
    
       Queue* queueInit(Queue* pQue)
       {
         pQue->first=(Qnode*)malloc(sizeof(Queue));
         pQue->first->data=-1;
         pQue->tail=pQue->first;
         return pQue;
       }
    
       Qnode* queuePull(Queue* pQue)
       {
         pQue->tail=pQue->tail->prev;
         return pQue->tail->next;
       }
    
       void queuePush(Queue* pQue, Qnode* pNode)
       {
         pNode->next=pQue->first;
         pQue->first->prev=pNode;
         pQue->first=pNode;
       }
    
       Queue* queueEmpty(Queue* pQue)
       {
         while(pQue->first!=pQue->tail)
         {
           Qnode* pCurr=pQue->first;
           pQue->first=pQue->first->next;
           free(pQue->first);
         }
         return pQue;
       }
    
       //图的声明
       typedef struct node
       {
         int adjvex;
         int hostvex;
         struct node *nextrarc;
         int info;
       }EdgeNode;
    
       typedef struct vnode
       {
         char vexdate;
         EdgeNode *firstarc;
       }VertexNode;
    
       typedef VertexNode AdjList[MaxVertexNum];
    
       typedef struct
       {
         AdjList adjlist;
         int n,e;
       }ALGraph;
    
       int initGraph(ALGraph* aGraph);
       int mFind(char aChar, ALGraph* aGraph);
       int createHead(char aChar, ALGraph* aGraph);
       void addBody(char aChar, int aPos, ALGraph* aGraph, int weight);
       void Kruskal(ALGraph* aGraph);
    
       int main(void)
       {
         char a;
         int isFinish=0;
         int headPos=-1;
         char a1='@', a2='@', a3='@', a4='@', a5='@', a6='@', a7='@';
         ALGraph g_graph;
         initGraph(&g_graph);
    
         printf("Input arcs like this '(start,end:weight)',end with $\n");
         while(isFinish==0)
         {
            while(1)
            {
              a=getchar();
              if(a=='$'||a=='#')
              {
                if(a=='#')
                  isFinish=1;
                break;
              }
              if(a==' '||a=='\n')
                continue;
              a1=a2;
              a2=a3;
              a3=a4;
              a4=a5;
              a5=a6;
              a6=a7;
              a7=a;
              if(a1=='('&&a3==','&&a5==':'&&a7==')')
              {
                if((headPos=mFind(a2,&g_graph))==-1)
                  headPos=createHead(a2,&g_graph);
                addBody(a4,headPos,&g_graph,a6);
              }
            }
         }
         Kruskal(&g_graph);
         return 0;
       }
    
       void Kruskal(ALGraph* aGraph)
        {
          int i,j,u1,v1,sn1,sn2,k;
          int vset[MaxVertexNum];
          EdgeNode* E[MaxVertexNum];
          k=0;
          for(i=0; i<aGraph->n; i++)
          {
            EdgeNode* temEdge;
            for(temEdge=aGraph->adjlist[i].firstarc; temEdge!=NULL;
                    temEdge=temEdge->nextrarc)
            {
              E[k]=temEdge;
              k++;
            }
          }
          //将边的权值进行排序
          for(i=0; i<aGraph->e; i++)
          {
            for(j=aGraph->e-1; j>i; j--)
              if(E[j]->info<E[j-1]->info)
              {
                EdgeNode* tem=E[j];
                E[j]=E[j-1];
                E[j-1]=tem;
              }
          }
          for(i=0; i<aGraph->n; i++)
            vset[i]=i;
          k=1;
          j=0;
          //添加边
          while(k<aGraph->n)
          {
            u1=E[j]->hostvex;
            v1=E[j]->adjvex;
            sn1=vset[u1];
            sn2=vset[v1];
            if(sn1!=sn2)
            {
              printf("(%d,%d):%c\n",u1,v1,E[j]->info);
              k++;
              for(i=0; i<aGraph->n; i++)
                if(vset[i]==sn2)
                  vset[i]=sn1;
            }
            j+=2;
          }
        }
    
        void addBody(char aChar, int aPos, ALGraph* aGraph, int weight)
        {
          int inversePos;
          EdgeNode* node=(EdgeNode*) malloc(sizeof(EdgeNode));
          node->info=weight;
          if((node->adjvex=mFind(aChar,aGraph))==-1)
            node->adjvex=createHead(aChar,aGraph);
          node->hostvex=aPos;
          node->nextrarc=NULL;
          if(aGraph->adjlist[aPos].firstarc==NULL)
            aGraph->adjlist[aPos].firstarc=node;
          else
          {
            EdgeNode* tail=aGraph->adjlist[aPos].firstarc;
            while(tail->nextrarc!=NULL)
              tail=tail->nextrarc;
            tail->nextrarc=node;
          }
          aGraph->e++;
    
          inversePos=node->adjvex;
          node=(EdgeNode*) malloc(sizeof(EdgeNode));
          node->info=weight;
          node->hostvex=inversePos;
          node->adjvex=aPos;
          node->nextrarc=NULL;
          if(aGraph->adjlist[inversePos].firstarc==NULL)
            aGraph->adjlist[inversePos].firstarc=node;
          else
          {
            EdgeNode* tail=aGraph->adjlist[inversePos].firstarc;
            while(tail->nextrarc!=NULL)
              tail=tail->nextrarc;
            tail->nextrarc=node;
          }
          aGraph->e++;
        }
    
       int createHead(char aChar, ALGraph* aGraph)
       {
         int currPos=aGraph->n;
         aGraph->adjlist[currPos].vexdate=aChar;
         aGraph->n++;
         return currPos;
       }
    
       int mFind(char aChar, ALGraph* aGraph)
       {
         int i=0;
         for(i=0; i<aGraph->n; i++)
         {
           if(aChar==aGraph->adjlist[i].vexdate)
             return i;
         }
         return -1;
       }
    
       int initGraph(ALGraph* aGraph)
       {
         int i=0;
         aGraph->e=0;
         aGraph->n=0;
         for(i=0; i<MaxVertexNum; i++)
         {
           aGraph->adjlist[i].firstarc=NULL;
         }
         return 0;
       }

程序运行结果截图如下：Ctrl+F5执行程序Kruskal.cpp

![Center 1][]

[Center]: /images/20220731/ff7f19a255994abcaf3d72c078444068.png
[SouthEast]: /images/20220731/79c5bd7665a5411887b6cdb452470138.png
[Center 1]: /images/20220731/ce334303a614435a8d0d32718dfc3917.png