prim-

1、猴子选大王 2、约瑟夫环 3、迷宫求解 4、回文游戏 5、地图四染色问题 6、八皇后问题 7、原四则表达式求值 8、k阶斐波那契序列 9、遍历二叉树 10、编写DFS算法的非递归

//Prim算法构造最小生成树

#include <iostream>
#include<iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define infinity 30000
#define MAX 20

int s[MAX];//U

typedef struct ArcCell{
  int adj;
}AecCell,AdjMatrix[MAX][MAX];

typedef struct Mgraph{
  char vex[MAX];
  AdjMatrix arcs;
  int vexnum,arcnum;
}Mgraph;

int Create(Mgraph&G)
{
   int i,j,value,n=0;
   int v1,v2; 
   int LocateVex(Mgraph G,char name);
   
   
   printf("input the number of the vertex:");
   scanf("%d",&G.vexnum);
   
   
   printf("input the number of the ArcCell:");
   scanf("%d",&G.arcnum);
   
   for(i=0;i<G.vexnum;i++)
    for(j=0;j<G.vexnum;j++)
       G.arcs[i][j].adj=infinity;//初始化
   
	
	printf("input the ArcCell:\n");
   
	for(j=0;j<G.arcnum;j++)
   {  
	  scanf("%d %d %d",&v1,&v2,&value);
      G.arcs[v1-1][v2-1].adj=G.arcs[v2-1][v1-1].adj=value;
   }
   return 1;
}



       

void prim(Mgraph G,int v0,int adjvex[],int lowcost[])
{ 
  int v,i,w,min;

  
  
  for(v=0;v<G.vexnum;v++)//辅助函数lowcost和adjvex初始化
  {
	  s[v]=0;//存储U中的点
      lowcost[v]=G.arcs[v0][v].adj;
      if(lowcost[v]<infinity)
		  adjvex[v]=v0;//将与v0相邻的点的adjvex值设为v0
	  else adjvex[v]=-1;//若不存在边，设为-1
  }
  lowcost[v0]=0;
  s[v0]=1;//add v0 to U
  
  
  for(i=1;i<G.vexnum;++i)
  { 
	  min=infinity;
	  for(w=0;w<G.vexnum;++w)//找到V-U中到U中的权值最小的边
		  if(s[w]==0)   //w∈V-U
			  if(lowcost[w]<min)
			  {
				  v=w;
			      min=lowcost[w];//找到权值最小的边，v记录它的点，min记录它的权值
			  }
			  
	  s[v]=1;//add v to U
			  
	  for(w=0;w<G.vexnum;++w)//校正V-U中点的lowcost值 
		  if(s[w]==0 &&(G.arcs[v][w].adj<lowcost[w]))//若w∈V-U且v和w组成的边的权值小雨lowcost[w]，则修改辅助数组
		  { 
			  lowcost[w]= G.arcs[v][w].adj;
			  adjvex[w]=v; 
		  }
  }


}

int main()
{
  int i,j;
  Mgraph G;
  //adjvex和lowcost共同构成辅助数组，记录点vi∈V-U到U中点的有最小权值的边 
  int adjvex[MAX];//i点依附的在U中的点
  int lowcost[MAX];//该边的权
  
  Create(G);
  
  printf("The ArcCell is:\n");
  i=0;
  
  prim(G,i,adjvex,lowcost);//从i=0点出发构造最小生成树
  
  
  for(j=1;j<G.vexnum;j++)
     printf("v%d -- v%d cost=%d;\n",j+1,adjvex[j]+1,lowcost[j]);
        
 	
  return 0;
}

//vexunm=6,arcnum=10
/*
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6
*/