prim.txt

prim算法的原理利用 prim算法构造最小生成树。有机的应用prim和数组存储生成树。

＃include <studio.h>      
#define Max 10
#define VertexNum 5
Struct List           /*节点结构声明*/
{
	Int marked;      /*查找标记*/
	Int vertex1;      /*顶点声明*/
	Int vertex2;      /*顶点声明*/
	Int weight;      /*加权值*/
	Struct list *next;
};
Typedef struct List node;
Typedet node *edge;    /*定义领接边的节点*/
Int edges[10][3]=     
	{{1,2,7},{1,3,6},{1,4,5},{1,5,12},{2,3,14},{2,4,8,},{2,5,8},{3,4,3},{3,5,9},{4,5,2}};
int visited[vertexnum+1];    /*查找记录*/

void prims(edge head, int index)
{
	Edge pointer;        /*节点声明*/
	Edge minedge;       
	Int edgenum=0;       /*已连结边的数目*/
	Int weight=0;         /*累计加权值*/
	Int i;             
	Visited[index]+1;    /*设置已查找过的*/
	While (edgenum!=(vertexnum-1))    /*当边的数目为顶点的数目减1的时候，结束循环*/
	{
	minedge->weight=999;      /*讲最小边的加权值设置为最大*/
	For (i=1;i<vertexnum;i++)       /*判断未建立的酃接顶点 */
	{
	Pointer=head;
	If (visited[i]==1)      /* 已存在生成数集合的顶点*/
	{
	While (pointer->marked==1)   /* 往下一个未建立的酃接边*/
	Pointer=pointer->next;  
	If (minedge->weight>pointer->weight)
	Minedge=pointer;         /*找出加权值最小的酃接边 */
	While(pointer!=null) 
	{
	/*如果两个顶点都存在生产树集合中，表示是已经查找过的边 */
	If (visited[pointer->vertex1]==1&&visited[pointer->vertex2]==1)
	/* 找出加权值最小的酃接边*/
	If (minedge->weight>pointer->weight && pointer->marked==0
	 && (pointer->vertex1==i || 
	pointer->vertex2==i ))
	Minedge=pointer;
	Pointer=pointer->next;
	}
	}
	}
	Visited[minedge->vertex1]=1;    /* 将顶点1设为存在生成树集合中*/
	Visited[minedge->vertex2]=1;    /*将顶点2设为存在生成树集合中*/
	Edgenum++;             /*生成树的边数＋1*/
	Weight+= minedge->weight;    /*累计加权值*/
	Printf(“[%d,%d]”,minedge->vertex1,minedge->vertex2);
	Printf(“(%d)”,minedge->weight);
	}
	Printf(“\nTotal weight=%d\n”,weight);      /*输出加权值总和*/
}

/*释放链表 */
Void free_edge(edge head)
{
	Edge pointer;              /*节点声明*/
	While (head!=null)            /*当节点为null的时候，结束循环*/
	{
	Pointer=head;
	Head=head.>next;        /*往下一个节点*/
	Free(pointer);
	}
	}

/*输出链表数据 */
Void print_edge(edge head)
{
	Edge pointer;        /*节点声明*/
	Pointer=head;            /*pointer指针设为首节点*/
	While (pointer!=null)         /*当节点为null的时候，结束循环*/
	{
	Printf(“[%d,%d]”,pointer->vertex1,pointer->vertex2);
	Printf(“(%d)”,pointer->weight);     /*输入加权值*/    
	Pointer=pointer->next;       /*往下一个节点*/ 
	}
	Printf(“\n”)
	}



/* 插入酃接边到链表中*/
Edge insert_edge(edge head, edge new)
{
	Edge pointer;              /*节点声明*/
	Pointer=head;             /*pointer指针设为首节点*/
	While (pointer->next!=null)       /*插入在链表的尾端*/
	Pointer=pointer->next;
	Pointer->next=new;
	Return head;
}

/*建立链表*/
Edge create_edge(edge head)
{
	Edge new;               /*节点声明*/
	Edge pointer;             /*节点声明*/
	Int I;
	Head=(edge)malloc(sizeof(node));         /*内存配置*/
	If (head==null)
	Printf(“memory allocate failure !!\n”);     /*内存配置失败*/
	Else
	{
	Head.>marked=0;
	Head.>vertex1=edge[0][0];
	Head.>vertex2=edge[0][1];
	Head.>weight=edge[0][2];           /*定义节点加权值*/
	Head.>next=null;
	For (i=1;i<=10;i++)
	{
	New=(edge) malloc (sizeof(node));
	If (new != null)
	{
	new.>marked=0;
	new.>vertex1=edges[i][0];
	new.>vertex2=edges[i][1];
	new.>weight=edges[i][2];      /*定义节点加权值*/
	new.>next=null;
	head=insert_edge(head,new);     /*插入新的节点*/
	}
	}
	}
	Return head;
}

/*主程序 */
Void main()
{
	Edge head;                   /*节点声明*/
	Int I;
	For (i=1;i<=vertexnum;i++)        /*清楚查找记录*/
	Visited[i]=0; 
	Head=create_edge(head);         /*调用建立链表*/
	Print_edge(head);
	If (head!=null)
	{
	printf(“prims algorithm:\n”);
	printf(“start from vertex 1.\n”);
	printf(“find minimal spanning tree.\n”);  
	prims(head,1);      /*调用prims算法*/
	free(head);       /*调用释放链表*/
	}
}