island.cpp

实现岛上建立公路的最短路径算法

/***********************************************************
//*****头部文件中的函数实现
************************************************************/
#include "island.h"

/***********************************************************
//*****图的初始化
************************************************************/
void GraphInit(struct MGraph &G,int v)
{
	int i,j;
	int **p,*q;
	i = j = 0;
	p = (int **)malloc(v*sizeof(int *));	//开邻接矩阵的列向量
	q=(int *)malloc(v*sizeof(int));
	while (i<v)								//邻接矩阵第一列的初始化
	{
		q[i] = i;
		i++;
	}
	G.vexs=q;
	G.vexnum=v;					//置顶点数
	i=0;
	while (i<v)					//邻接矩阵的初始化
	{
		*(p+i) = (int *)malloc(v*sizeof(int));	//循环开行向量
		while (j<v)
		{
			*(*(p+i)+j)=MAX;		//初始化元素
			j++;
		}
		j = 0;
		i++;
	}
	G.arcs = p;
}

/***********************************************************
//*****Prim算法中求每个结点周围的最小权值结点
************************************************************/
int minimum(struct Close closedge[],int v)
{
	int min,j,re=0;
	j=1;
	min = MAX;			
	while (j<v)
	{
		if (closedge[j].lowcost<min && closedge[j].lowcost != -1)	//循环求最小值
		{
			min = closedge[j].lowcost;
			re = j;
		}
		else
			if (closedge[j].lowcost==0)				//如果已经有边存在，返回此边的序号
			{
				return j;
			}
		j++;
	}
	return re;
}

/***********************************************************
//*****Prim算法求最小生成树，返回权值总和
************************************************************/
int Mini_SpanTree_PRIM(struct MGraph G,int v)
{
	int i,k,j;
	int total;                                               //int s=0;
	total = k = i = j = 0;
	struct Close *closedge;
	closedge = (struct Close*)malloc(v*sizeof(struct Close));	//辅助数组开空间
	for (j = 0;j<G.vexnum;++j)			//辅助数组初始化
	{
		if(j!=k)
		{
			closedge[j].adjvex = 0;
			closedge[j].lowcost = *(*(G.arcs+k)+j);
		}
	}
	closedge[k].lowcost = -1;			

	for (i=1;i<G.vexnum;i++)			//依次加入其余的G.vexnum-1个顶点
	{									// while (s<G.vexnum){printf(" %d ",closedge[s].lowcost);s++;if(s==G.vexnum)putchar('\n');}s=0;
		k = minimum(closedge,G.vexnum);	//找到（非负）lowcost最小边的关联顶点k，它就是MST的下一个顶点
		total += closedge[k].lowcost;	//求和
		closedge[k].lowcost=-1;			//顶点k并入U集
		for (j=0;j<G.vexnum;j++)		//扫描所有顶点
		{
			if (G.arcs[k][j]<closedge[j].lowcost)//如果该顶点到U的距离可以缩短
			{
				closedge[j].lowcost = *(*(G.arcs+k)+j); //已在U中的顶点，lowcost将不会被修改
				closedge[j].adjvex = G.vexs[k];
			}
		}
	}
	return total;
}