MST最小生成木及びPrimプルームアルゴリズム

MSTは前でKruskalアルゴリズムを学び、Primというアルゴリズムもあります.この両者の違いはPrimアルゴリズムが稠密図に適していることであり,例えば鳥の巣というほとんどの点がつながっている図である.その時間的複雑度はO(n^2)であり、その時間的複雑度はエッジの数とは無関係である.一方kruskalアルゴリズムの時間複雑度はO(eloge)であり,エッジの数に関係し,疎図に適している.
primアルゴリズム
基本思想:G=(V,E)が連通していると仮定し,TEはG上の最小生成ツリーの中辺の集合である.アルゴリズムはU={u 0}(u 0∈V),TE={空セット}から始まる.次の操作を繰り返します.
    1.すべてのu∈U,v∈V−Uのエッジ(u,v)∈Eの中で重み値が最も小さいエッジ(u 0,v 0)を探して集合TEに組み込み、同時にv 0はV=UまでUに組み込みます.次はv 0を辺とする起点で,重み値が最も小さい辺を探し続け集合TEに組み込み,順次往復する.
    2.最後に,TEには必ずn−1辺があり,T=(V,TE)はGの最小生成木である.
Primアルゴリズムの核心:常にTEの中の辺集を維持して1本の生成木を構成して、つまりそれとKruskalアルゴリズムの主な違いは、Primはずっと1種の直列の状態を維持して全体の貪欲なアルゴリズムに従わないことです.実は初期点uoの選択は自由で、一般的に問題を解く条件は最小の重み値の辺を与えるか取ることができます.
実装されるコードは次のとおりです.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define infinity 1000000
#define max_vertexes 6 

typedef int Graph[max_vertexes][max_vertexes];

void prim(Graph G,int vcount,int father[])
{    
int i,j,k; 
int lowcost[max_vertexes];
int closeset[max_vertexes],used[max_vertexes];
int min;  
for (i=0;i<vcount;i++)     
  {
/*              1       */   
    lowcost[i]=G[0][i];
    /*                1    */
     closeset[i]=0;      
  used[i]=0;    
    father[i]=-1;      
}    
used[0]=1; /*       s    */
/* vcount       vcount-1          */  
  for (i=1;i<=vcount-1;i++)      
   {       
 j=0;
     min = infinity;
       /*               k */      
     for (k=1;k<vcount;k++)
         /*              */     
 if ((!used[k])&&(lowcost[k]<min)) 
    {
              min =  lowcost[k];
              j=k;
            }       
    father[j]=closeset[j];   
printf("%d %d
",j+1,closeset[j]+1);//      
used[j]=1;;//  j      U      
for (k=1;k<vcount;k++)
         /*         */       
   if (!used[k]&&(G[j][k]<lowcost[k]))       
{ 
                  lowcost[k]=G[j][k];/*      */       
      closeset[k]=j;;/*       */
    }      
   }
}
                 
int main()
{
FILE *fr;
int i,j,weight;
Graph G;
int fatheer[max_vertexes];
for(i=0; i<max_vertexes; i++)
for(j=0; j<max_vertexes; j++)
G[i][j] = infinity;
fr = fopen("prim.txt","r");
if(!fr)
{
printf("fopen failed
");
exit(1); 
}
while(fscanf(fr,"%d%d%d", &i, &j, &weight) != EOF)
{
G[i-1][j-1] = weight;
G[j-1][i-1] = weight;
}
prim(G,max_vertexes,fatheer);
return 0;
}

隣接行列の形式で記憶の実現を行う:

#include <stdio.h>
#define n 6
#define MaxNum 10000  /*        */

/*        */
typedef int adjmatrix[n+1][n+1];   /*0     */

typedef struct{
	int fromvex,tovex;
	int weight;
}Edge;
typedef Edge *EdgeNode;

int arcnum;     /*    */

/*        */
void CreatMatrix(adjmatrix GA){
	int i,j,k,e;
	printf("   %d   
",n);
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(i==j){
				GA[i][j]=0;         /*       0*/
			}
			else{
				GA[i][j]=MaxNum;    /*                 */
			}
		}
	}
	printf("       ：");
	scanf("%d",&arcnum);
	printf("       ，    ，  ，       ：
");
	for(k=1;k<=arcnum;k++){
		scanf("%d,%d,%d",&i,&j,&e);  /*      */
		GA[i][j]=e;
		GA[j][i]=e;
	}
}

/*         */
void InitEdge(EdgeNode GE,int m){
	int i;
	for(i=1;i<=m;i++){
		GE[i].weight=0;
	}
}

/*                */
void GetEdgeSet(adjmatrix GA,EdgeNode GE){
	int i,j,k=1;
	for(i=1;i<=n;i++){
		for(j=i+1;j<=n;j++){
			if(GA[i][j]!=0&&GA[i][j]!=MaxNum){
				GE[k].fromvex=i;
				GE[k].tovex=j;
				GE[k].weight=GA[i][j];
				k++;
			}
		}
	}
}

/*           */
void SortEdge(EdgeNode GE,int m){
	int i,j,k;
	Edge temp;
	for(i=1;i<m;i++){
		k=i;
		for(j=i+1;j<=m;j++){
			if(GE[k].weight>GE[j].weight){
				k=j;
			}
		}
		if(k!=i){
			temp=GE[i];GE[i]=GE[k];GE[k]=temp;
		}
	}
}

/*           v                 */
void Prim(adjmatrix GA,EdgeNode T){
	int i,j,k,min,u,m,w;
	Edge temp;
	/* T   ，   v1          */
	k=1;
	for(i=1;i<=n;i++){
		if(i!=1){
			T[k].fromvex=1;
			T[k].tovex=i;
			T[k].weight=GA[1][i];
			k++;
		}
	}
	/*  n-1   ，            k  */
	for(k=1;k<n;k++){
		min=MaxNum;
		m=k;
		for(j=k;j<n;j++){
			if(T[j].weight<min){
				min=T[j].weight;m=j;
			}
		}
		/*       k-1    */
		temp=T[k];
		T[k]=T[m];
		T[m]=temp;
		/*         T        j*/
		j=T[k].tovex;
		/*     ， T  T                    */
		for(i=k+1;i<n;i++){
			u=T[i].tovex;
			w=GA[j][u];
			if(w<T[i].weight){
				T[i].weight=w;T[i].fromvex=j;
			}
		}
	}
}

/*          */
void OutEdge(EdgeNode GE,int e){
	int i;
	printf("    ，  ，              ：
");
	for(i=1;i<=e;i++){
		printf("%d,%d,%d
",GE[i].fromvex,GE[i].tovex,GE[i].weight);
	}
}

void main(){
	adjmatrix GA;
	Edge GE[n*(n-1)/2],T[n];
	CreatMatrix(GA);
	InitEdge(GE,arcnum);
	GetEdgeSet(GA,GE);
	SortEdge(GE,arcnum);
	Prim(GA,T);
	printf("
");
	OutEdge(T,n-1);
}