破圈法求解最小生成树c语言实现（已验证）-白红宇

破圈法求解最小生成树c语言实现（已验证）

阅读量：6032 次

发布时间：2019-06-20

本文共 3074 字，大约阅读时间需要 10 分钟。

破圈法求解最小生成树c语言实现（已验证）

下面是算法伪代码，每一个算法都取一个图作为输入，并返回一个边集T。

对该算法，证明T是一棵最小生成树，或者证明T不是一棵最小生成树。此外，对于每个算法，无论它是否能计算出一棵最小生成树，都要给出其最有效的实现。

MAYBE-MST-A(G，w)Sort the edges into nonincreasing order of edge weights wT<-EFor each edge e, taken in nonincreasing order by weightDo if T-{e} is a connected graph    Then T<-T-eReturn T

算法基本思想：

先将图G的边按照权的递减顺序排列后，依次检验每条边，在保持连通的情况下，每次删除最大权边，直到所有边都被遍历到无法删除任何一边（或余下n-1条边为止）。

证明：

生成树证明：

1、 如果给定连通图G没有回路，那么G本身就是一棵生成树

2、 如果G中只有一个回路，则删去G的回路上的一条边（不删除节点），则产生的图仍是连通的且没有回路，则得到的子图就是G的一棵生成树；

3、 如果G的回路不止一个，只要删去每一个回路上的一条边，知道G的子图是连通且没有回路且与图G有一样的结点集，那么这个子图就是一棵生成树。

4、 重复步骤3，则直到所有边都不能删除，由于删除判断条件，得到的子图就是一棵生成树。

MST证明：

若在某个回路C中有一条唯一的最长边，则T^*中一定不含这条边，因为优先删除回路中最长的边。

若在某个边e的割集中有一条唯一一条最短边，则T^*中一定含有这条边（The Cut Property：考虑图G中的一条边e。如果存在一个cut(A,B)，使得e是所有跨越该割的所有边中权重最小者，则e一定在G的MST中。

），且不含有其他边，因为一旦含有其他边就构成了回路（Lonely-Cut Corollary：如果边e是跨越了cut(A, B)的唯一一条边,则e不可能在任一圈中。）。

反向证明：假设T^*中跨越cut（A,B）的边不只一条，则在算法结束之前一定会遍历到其中的成圈的边（Double-Crossing），根据权值选取方法和删除圈的一边仍为连通图的条件，一定会将权值较大的边删除，直到无环且剩下的唯一一条边是最短边。

算法变量：

a[n][n]:带权图的邻接矩阵,a[i][j]=w或a[i][j]=0；

max:标记当前找到的准备删去的边的权值；

p:标记找到的要删去的权值所在的行号；

q:标记找到的要删去的权值所在的列好；

am：标记找到的最大元素（am是为了保护权值大但不能删的边），如果a[i][j]不能删除，则可以让a[p][q]=am，a[q][p]=am来还原刚才删去的边；

I,j:二维数组的行号和列号

sm:图的边数，每删除一个边，sm就减1，当sm=n-1时，结束

wt：最小生成树的权值和

算法实现（c语言）

1 #include
     
           BY Yuanshuai Zheng,UESTC  2 #define n 5  3 int a[n][n];  4 int flag,am,p,q;  5 INPUT()  6 {  7     int i,j;  8     printf("输入图的带权邻接矩阵：\n");  9     for(i = 0;i
      
       max)&&(a1[i][j]<=am1)&&((i!=p1)||(j!=q1))) 34          { 35              max = a1[i][j]; 36              ptm = i; 37              qtm = j; 38  39         } 40      } 41     am = max; 42     printf("max=%5d\t",am); 43      p = ptm; 44      q = qtm; 45      a[p][q]=0; 46      a[q][p]=0; 47  } 48  WSHALL(int array[n][n]) 49  { 50      int i,j,k,m=0; 51      int r[n][n],B[n][n]; 52      for(i=0;i
       
        =1) 60                 B[i][j]=1; 61             else  62                 B[i][j]=0;  63             //分界线  64          } 65      } 66     for(j=0;j
        
         =1) 70                 { 71                     for(k=0;k
         
          =1) 74                             { 75                                 B[k][j]=B[j][k]=1; 76                             } 77                         } 78                 } 79     } 80     for(i=0;i
          
           =1)||(i==j))103 // m=m+1;104 // }105 // }106 // }107 // printf("m=%d\t",m);108 // if(m==n*n)109 // flag = 1;110 // else111 // flag=0;112 // return(flag);113 114 int main()115 {116 int i,j,sm,wt=0;117 am = 10000,p=-1,q=-1,sm=0;118 INPUT();119 for(i=0;i
           
            0)124 sm = sm+1;125 }126 }127 printf("\nsm=%d\n",sm);128 printf("输出图的带权邻接矩阵：\n");129 OUTPUT(a);130 printf("\n");131 while(sm>n-1)132 {133 MAX(a,am,p,q);134 flag=WSHALL(a);//华沙尔算法判断是否连通 135 //printf("flag= %d",flag);136 {137 if(flag==1)138 {139 sm=sm-1;140 //printf("flag= %d",flag);141 } 142 else143 {144 a[p][q]=am;145 a[q][p]=am;146 }147 }148 }149 for(i=0;i

代码验证：

例子：

转载于:https://www.cnblogs.com/zysps1/p/poquanfa_mst.html

你可能感兴趣的文章