用普里姆（Prim）算法构造最小生成树

C语言，数据结构作业 用普里姆(Prim)算法构造最小生成树

#include 


#define INFINITY INT_MAX  
#define MAX_VERTEX_NUM 20  

enum GraphKind{DGDNUDGUDN};      //图的类型



 
typedef struct 
{
    int weight;                                     //权值
}ArcCellAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 二维数组 

typedef struct  
{ 
    char vexs[MAX_VERTEX_NUM];  
    AdjMatrix arcs;  
    int vexnumarcnum;  
    GraphKind kind;  
}Graph; 


int LocateVex（Graph Gchar u） 
{  
    for（int i=0;i        if（G.vexs[i]==u） 
            return i; 
        return -1; 
} 

void CreateUDN（Graph &G） 
{  
    
	int ijk;
	int weight;
    char vavb;
    printf（“请输入无向图G的顶点数边数\n“）; 
    scanf（“%d%d“&G.vexnum&G.arcnum）; 
	getchar（）;

    printf（“请输入 %d 个顶点的值:\n“G.vexnum）; 
    for（i=0;i	{
		printf（“请输入第 %d 个顶点的值:\n“i+1）;
        scanf（“%c“&G.vexs[i]）; 
		getchar（）;
	}
	
    for（i=0;i        for（j=0;j        { 
			if（i!=j）
				G.arcs[i][j].weight=1000;
			else
				G.arcs[i][j].weight=0;  
        } 
		
        printf（“请输入 %d 条边的两个顶点及边权值:\n“G.arcnum）; 
        for（k=0;k        { 
			printf（“请输入第 %d 条边的两个顶点及权值:\n“k+1）;
            scanf（“%c%c%d“&va&vb&weight）;
			getchar（）;
			
            i=LocateVex（Gva）; 
            j=LocateVex（Gvb）; 
            G.arcs[i][j].weight=G.arcs[j][i].weight=weight; // 无向图 
        } 

        G.kind=UDN; 
} 

int FirstAdjVex（Graph Gchar v） 
{  
    int ik; 
    k=LocateVex（Gv）; 
    for（i=0;i        if（G.arcs[k][i].weight!=0） 
            return i; 
        return -1; 
} 
 
int NextAdjVex（Graph Gchar vchar w） 
{  
    int ik1k2; 
    k1=LocateVex（Gv）;  
    k2=LocateVex（Gw）;  
    for（i=k2+1;i        if（G.arcs[k1][i].weight!=0） 
            return i; 
        return -1; 
} 

void MiniSpanTree_P（Graph G char u）
{
	struct
	{
		char	adjvex;				// U集中的顶点序号
		int    lowcost;				// 边的权值
	} closedge [MAX_VERTEX_NUM];

	int ijknlm;
	
	//用普里姆算法从顶点u出发构造网G的最小生成树

	k = LocateVex （Gu）; 
	
	for （j=0;j		if （j!=k） 
		{
			closedge[j].adjvex=u;
			closedge[j].lowcost=G.arcs[k][j].weight;
		}

		closedge[k].lowcost = 0;			// 初始，U＝{u}

	
		for （m=1;m		{
			k=100;
			for（i=0;i			{
				if（（closedge[i].lowcost!=0）&&（k>closedge[i].lowcost））
				{
					k=closedge[i].lowcost;
					l=i;
				}
			} 
									
			printf（“%c%c\n“closedge[l].adjvex G.vexs[l]）;
			
			closedge[l].lowcost = 0;    // 第k顶点并入U集

			for （j=0;j				if （G.arcs[l][j].weight				{
						closedge[j].adjvex=G.vexs[l];
						closedge[j].lowcost=G.arcs[l][j].weight;
				}
				
		}
}

void main（）
{
	Graph G;
	CreateUDN（G）;
	MiniSpanTree_P（G‘1‘）;
	
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     184394  2008-11-30 22:27  Prime\Debug\Prime.exe

     文件     353280  2008-11-30 22:27  Prime\Debug\Prime.pdb

     文件     184393  2008-12-01 12:31  Prime\Debug\Test.exe

     文件       9429  2008-12-01 12:31  Prime\Debug\Test.obj

     文件     443392  2008-12-01 12:31  Prime\Debug\Test.pdb

     文件      53248  2008-12-01 12:31  Prime\Debug\vc60.pdb

     文件       3035  2008-12-01 12:31  Prime\Prime.cpp

     文件       4210  2008-11-30 22:26  Prime\Prime.dsp

     文件        535  2008-11-30 22:26  Prime\Prime.dsw

     文件      25600  2008-11-30 22:36  Prime\Prime.ncb

     文件          0  2008-11-30 22:36  Prime\Prime.plg

     文件       3377  2008-12-01 12:29  Prime\Test.dsp

     文件        533  2008-12-01 12:36  Prime\Test.dsw

     文件      41984  2008-12-01 12:36  Prime\Test.ncb

     文件      48640  2008-12-01 12:36  Prime\Test.opt

     文件        736  2008-12-01 12:31  Prime\Test.plg

     目录          0  2009-09-21 22:09  Prime\Debug

     目录          0  2009-09-21 22:09  Prime

----------- ---------  ---------- -----  ----

              1356786                    18