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

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

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

这里说下最小连通网的Prim算法：

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

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

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

而Kruskal算法，http://blog.****.net/nethanhan/article/details/10050735有介绍，大家可以去看下!

 

Prim算法代码:

[cpp] view plain copy
  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3.   
  4. /* run this program using the console pauser or add your own getch, system("pause") or input loop */  
  5.   
  6. #define VNUM 9  
  7. #define MV 65536  
  8.   
  9. int P[VNUM];//记录边   
  10. int Cost[VNUM];//存储每一条边所要耗费的成本   
  11. int Mark[VNUM];//标记顶点   
  12. int Matrix[VNUM][VNUM] =  
  13. {//图   
  14.     {0, 10, MV, MV, MV, 11, MV, MV, MV},  
  15.     {10, 0, 18, MV, MV, MV, 16, MV, 12},  
  16.     {MV, 18, 0, 22, MV, MV, MV, MV, 8},  
  17.     {MV, MV, 22, 0, 20, MV, 24, 16, 21},  
  18.     {MV, MV, MV, 20, 0, 26, MV, 7, MV},  
  19.     {11, MV, MV, MV, 26, 0, 17, MV, MV},  
  20.     {MV, 16, MV, 24, MV, 17, 0, 19, MV},  
  21.     {MV, MV, MV, 16, 7, MV, 19, 0, MV},  
  22.     {MV, 12, 8, 21, MV, MV, MV, MV, 0},  
  23. };  
  24.   
  25. void Prim(int sv) // O(n*n)  
  26. {  
  27.     int i = 0;//循环变量   
  28.     int j = 0;//循环变量  
  29.       
  30.     if( (0 <= sv) && (sv < VNUM) )  
  31.     {  
  32.         for(i=0; i<VNUM; i++)  
  33.         {  
  34.             Cost[i] = Matrix[sv][i];//初始动点与其它顶点相连边的权值赋给cost数组  
  35.             P[i] = sv;//保存边   
  36.             Mark[i] = 0;//初始化标记   
  37.         }  
  38.           
  39.         Mark[sv] = 1;//标记顶点   
  40.           
  41.         for(i=0; i<VNUM; i++)  
  42.         {   
  43.             int min = MV;  
  44.             int index = -1;  
  45.               
  46.             for(j=0; j<VNUM; j++)  
  47.             {//挑选最小权值的边  
  48.                 if( !Mark[j] && (Cost[j] < min) )  
  49.                 {//挑选完毕以后，index保存另一个顶点   
  50.                     min = Cost[j];  
  51.                     index = j;  
  52.                 }  
  53.             }  
  54.               
  55.             if( index > -1 )  
  56.             {//如果为真，则说明照到最小值   
  57.                 Mark[index] = 1;  
  58.                   
  59.                 printf("(%d, %d, %d)\n", P[index], index, Cost[index]);  
  60.             }  
  61.               
  62.             for(j=0; j<VNUM; j++)  
  63.             {//从刚才被标记的顶点作为起始顶点   
  64.                 if( !Mark[j] && (Matrix[index][j] < Cost[j]) )  
  65.                 {//然后从新的起始顶点与其他顶点（非标记顶点）相连边的权值中寻找更小的，更新cost数组   
  66.                     Cost[j]  = Matrix[index][j];  
  67.                     P[j] = index;//如果有其它更小的，那么此边的起始顶点为P[i]，也就是index，权值保存在cost数组中   
  68.                 }  
  69.             }  
  70.         }  
  71.     }  
  72. }  
  73.   
  74. int main(int argc, char *argv[])   
  75. {  
  76.          Prim(0);  
  77.       
  78.     return 0;  
  79. }  

相关推荐