您的位置: 首页  >  文章  >  数据结构之n--n（kruskal算法）

数据结构之n--n（kruskal算法）

分类: 文章 • 2025-05-04 16:47:10

数据结构之n--n（kruskal算法）

数据结构之n--n（kruskal算法）

数据结构之n--n（kruskal算法）

数据结构之n--n（kruskal算法）

数据结构之n--n（kruskal算法）数据结构之n--n（kruskal算法）

上代码：如果有疑问的话，欢迎随时留言！

[cpp] view plain copy
  1. #include <stdio.h>  
  2.   
  3.   
  4. //闹了好长时间才闹好，如果有不懂的地方可以留言  
  5. //里面判断环的地方用到并查集  
  6.   
  7. //并查集资料：<a target="_blank" href="http://dongxicheng.org/structure/union-find-set/">http://dongxicheng.org/structure/union-find-set/</a>  
  8. #define ENUM 15//边的数量   
  9. #define VNUM 9//顶点的数量   
  10. #define MV 0  
  11.   
  12. typedef struct _tag_Edge //存储边的信息  
  13. {  
  14.     int begin;  
  15.     int end;  
  16.     int weight;//权值   
  17. }Edge;  
  18.   
  19. int father[VNUM]; //存储   
  20. int son[VNUM];  
  21. int Matvix[VNUM][VNUM]=  
  22. {//图   
  23.     {0, 10, MV, MV, MV, 11, MV, MV, MV},  
  24.     {10, 0, 18, MV, MV, MV, 16, MV, 12},  
  25.     {MV, 18, 0, 22, MV, MV, MV, MV, 8},  
  26.     {MV, MV, 22, 0, 20, MV, 24, 16, 21},  
  27.     {MV, MV, MV, 20, 0, 26, MV, 7, MV},  
  28.     {11, MV, MV, MV, 26, 0, 17, MV, MV},  
  29.     {MV, 16, MV, 24, MV, 17, 0, 19, MV},  
  30.     {MV, MV, MV, 16, 7, MV, 19, 0, MV},  
  31.     {MV, 12, 8, 21, MV, MV, MV, MV, 0},  
  32. };  
  33.   
  34. void swap(Edge array[], int i, int j)  
  35. {  
  36.     Edge temp = array[i];      
  37.     array[i] = array[j];     
  38.     array[j] = temp;  
  39. }  
  40.   
  41. void SelectionSort(Edge array[], int len) // O(n*n)  
  42. {  
  43.     int i = 0;  
  44.     int j = 0;  
  45.     int k = -1;  
  46.       
  47.     for(i=0; i<len; i++)  
  48.     {  
  49.         k = i;         
  50.         for(j=i; j<len; j++)  
  51.         {  
  52.             if( array[j].weight < array[k].weight )  
  53.             {  
  54.                 k = j;  
  55.             }  
  56.         }          
  57.         swap(array, i, k);  
  58.     }  
  59. }  
  60.   
  61. int unionsearch(int x) //查找根结点+路径压缩  
  62. {  
  63.     if(x != father[x])  
  64.     {//通过递归找到根结点，注意边最终的end为根结点   
  65.         father[x] =    unionsearch(father[x]);  
  66.     }  
  67.     //father[x]为x的父结点   
  68.     return father[x];  
  69. }  
  70.   
  71. int join(int x, int y) //合并  
  72. {  
  73.     int root1, root2;  
  74.     root1 = unionsearch(x);  
  75.     root2 = unionsearch(y);  
  76.     if(root1 == root2) //为环  
  77.         return 0;  
  78.     else   
  79.     {   //root2为root1的父结点   
  80.         father[root1] = root2;  
  81.         son[root2] += son[root1];  
  82.     }  
  83.   
  84.     return 1;  
  85. }  
  86.   
  87. int main()  
  88. {  
  89.         int i, j;//要使用的循环变量   
  90.         int total = 0;//最后选出边的数量   
  91.         int sum = 0;//最后总权值   
  92.         int flag = 0;  
  93.         int eNUM = ENUM-1;  
  94.           
  95.         Edge array[ENUM];//总共的边  
  96.            
  97.         for(i=0; i<VNUM; ++i) //初始化  
  98.         {  
  99.             father[i] = i;  
  100.             son[i] = 1;  
  101.         }  
  102.                 
  103.         for(i=0; i<VNUM; i++)  
  104.         {  
  105.             for(j=0; j<VNUM; j++)  
  106.             {  
  107.                 if((i<j) && (0 < Matvix[i][j]))  
  108.                 {//给边的结构体初始化   
  109.                     array[eNUM].begin = i;  
  110.                     array[eNUM].end   = j;  
  111.                     array[eNUM--].weight= Matvix[i][j];  
  112.                 }  
  113.             }  
  114.         }   
  115.           
  116.         //排序 ，对边按照权值排序，从小到大   
  117.         SelectionSort(array, ENUM);  
  118.           
  119.         for(i=0; i<ENUM; i++)  
  120.         {      
  121.             if(join(array[i].begin, array[i].end))  
  122.             {//判断是否成环  
  123.                 total++; //边数加1  
  124.                 sum += array[i].weight; //记录权值之和  
  125.                 printf("%d -> %d  weight:%d\n", array[i].begin, array[i].end, array[i].weight);  
  126.             }  
  127.             if(total == VNUM-1) //最小生成树条件：边数=顶点数-1  
  128.             {  
  129.                 flag = 1;  
  130.                 break;  
  131.             }  
  132.         }  
  133.         if(flag)  
  134.             printf("%d\n", sum);  
  135.         else  
  136.             printf("error.\n");  
  137.   
  138.         return 0;  
  139. }  

相关推荐