主程序.cpp

用于数据结构课程设计的,是一个办公室建局域网的利益最小化

# include <stdio.h>
# include "grah.h"
# define INF 32767                             /*INF表示无穷大*/
extern void DispMat(MGraph);                   /*外部函数*/
void Prim(MGraph g,int v)
{
	int lowcost[MAXV],min,n=g.vexnum;
	int closest[MAXV],i,j,k;
	for(i=0;i<n;i++)                           /*给lowcost[]和closest[]置初值*/
	{
		lowcost[i]=g.edges[v][i];
		lowcost[v]=0;                          /*将lowcost[v]置0*/
		closest[i]=v;
	}
	for(i=1;i<n;i++)                           /*找出n-1个顶点*/
	{
		min=INF;
		for(j=0;j<n;j++)                       /*在(V-U)中找出离最近的顶点k*/
			if(lowcost[j]!=0&&lowcost[j]<min)
			{
				min=lowcost[j];k=j;
			}
		printf("办公室(%d,%d)之间的布线成本为:%d\n",closest[k],k,min);
		lowcost[k]=0;                          /*标记k已经加入U*/
		for(j=0;j<n;j++)                       /*修改数组lowcost和closest*/
			if(g.edges[k][j]!=0&&g.edges[k][j]<lowcost[j])
			{
				lowcost[j]=g.edges[k][j];closest[j]=k;
			}
	}
}
void main()
{
	int i,j;
	MGraph g;
	int A[MAXV][10];
	g.vexnum=10;g.arcnum=45;
	for(i=0;i<g.vexnum;i++)
		A[i][i]=INF;
	A[0][1]=23; A[0][2]=12; A[0][3]=3;  A[0][4]=9;  A[0][5]=26; A[0][6]=26; A[0][7]=5;  A[0][8]=78; A[0][9]=46;
	A[1][2]=53; A[1][3]=1;  A[1][4]=63; A[1][5]=11; A[1][6]=54; A[1][7]=65; A[1][8]=94; A[1][9]=33;
    A[2][3]=2;  A[2][4]=25; A[2][5]=2;  A[2][6]=2;  A[2][7]=95; A[2][8]=22; A[2][9]=1;
	A[3][4]=64; A[3][5]=19; A[3][6]=23; A[3][7]=23; A[3][8]=4;  A[3][9]=6;
	A[4][5]=23; A[4][6]=10; A[4][7]=3;  A[4][8]=6;  A[4][9]=45;
	A[5][6]=15; A[5][7]=15; A[5][8]=83; A[5][9]=17;
	A[6][7]=7;  A[6][8]=82; A[6][9]=21;
	A[7][8]=89; A[7][9]=24;
	A[8][9]=4;
	for(i=0;i<g.vexnum;i++)
		for(j=0;j<g.vexnum;j++)
			A[j][i]=A[i][j];
    for(i=0;i<g.vexnum;i++)                    /*建立邻接矩阵*/
		for(j=0;j<g.vexnum;j++)
			g.edges[i][j]=A[i][j];
	printf("\n");
	printf("各办公室间的布线成本为:\n");
	DispMat(g);
    printf("\n");
	printf("普里姆算法求解得的办公室间的局域网:\n");
	Prim(g,0);
    printf("\n");
}