最小权值路径选择之普里姆算法以及克鲁斯卡尔算法之伪代码

//普里姆算法

#define Max 9#define NaN 655535apex[Max] = {v0,v1,v2,v3,v4,v5,v6,v7,v8};pic[Max][Max]={//   v0   v1   v2    v3    v4    v5   v6    v7    v8/*v0*/  0,  10,  NaN,  NaN,  NaN,  11,  NaN,  NaN,  NaN,/*v1*/ 10,   0,   18,  NaN,  NaN, NaN,   16,  NaN,   12,/*v2*/ NaN,  18,    0,   22,  NaN,  11,  NaN,  NaN,    8,/*v3*/ NaN, NaN,   22,    0,   20, NaN,   24,  NaN,   21,/*v4*/ NaN, NaN,  NaN,   20,    0,  26,  NaN,  NaN,  NaN,/*v5*/ 11, NaN,  NaN,  NaN,   26,   0,   17,  NaN,  NaN,/*v6*/ NaN, NaN,  NaN,  NaN,  NaN,  17,    0,  NaN,  NaN,/*v7*/ NaN, NaN,  NaN,   16,    7, NaN,   19,    0,  NaN,/*v8*/ NaN, NaN,    8,   21,  NaN, NaN,  NaN,  NaN,    0,}void PRim(int *apex,int (*pic)[Max]);void Prim(int *apex,int (*pic)[Max]){int adjex[Max];  //相关 int cast[Max];//权值 int i,j=1;int k=0;int min;for(i=0;i<Max;i++){adjex[i]=0;cast[i]=pic[k][i];}while(j<Max){k=0;min=NaN;for(i=1;i<Max;i++){if(cast[i]!=0&&cast[i]<min){min=cast[i];k=i;}}printf("%d,%d",adjex[k],k);cast[k]=0;for(i=0;i<Max;i++){if(cast[i]!=0&&pic[k][i]<cast[i]){adjex[i]=k;cast[i]=pic[k][i];} }j++;}}

//克鲁斯卡尔算法

#define Max 9#define NaN 655535apex[Max] = {v0,v1,v2,v3,v4,v5,v6,v7,v8};pic[Max][Max]={//   v0   v1   v2    v3    v4    v5   v6    v7    v8/*v0*/  0,  10,  NaN,  NaN,  NaN,  11,  NaN,  NaN,  NaN,/*v1*/ 10,   0,   18,  NaN,  NaN, NaN,   16,  NaN,   12,/*v2*/ NaN,  18,    0,   22,  NaN,  11,  NaN,  NaN,    8,/*v3*/ NaN, NaN,   22,    0,   20, NaN,   24,  NaN,   21,/*v4*/ NaN, NaN,  NaN,   20,    0,  26,  NaN,  NaN,  NaN,/*v5*/ 11, NaN,  NaN,  NaN,   26,   0,   17,  NaN,  NaN,/*v6*/ NaN, NaN,  NaN,  NaN,  NaN,  17,    0,  NaN,  NaN,/*v7*/ NaN, NaN,  NaN,   16,    7, NaN,   19,    0,  NaN,/*v8*/ NaN, NaN,    8,   21,  NaN, NaN,  NaN,  NaN,    0,}typedef struct pic{int begin;int end;int value;}pic;pic edg[15];//假设所有权值已经输入到edg里面，并且已经按照value从小到大排好序了 void find(int *parent,int f);void find(int *parent,int f){while(parent[f]>0){f=parent[f]; } return f;} void  Kruskal(pic *edg);void  Kruskal(pic *edg){int parent[Max];int i,j,m,n;for(i=0;i<Max;i++){parent[i]=0;}for(j=0;j<Max;j++){n=find(parent[j],edg[j].begin);m=find(parent[j],edg[j].end);if(n!=m){parent[j]=m;}}}