adjmlist.cpp

用Kruskal算法实现若干个城市之间的最短路径.最大城市数目为7个.

// adjMList.cpp: implementation of the adjMList class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "adjMList.h"
#include "iostream.h"
#include<iomanip.h>
#include<stdlib.h>
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

adjMList::adjMList(edge GE[],int v,int e)
{
	int i,j;
	for(i=0; i<v; i++)
	{
		for(j=0; j<v; j++)
		{
			if(j==i) GA[i][j]=0;
			else GA[i][j]=MaxValue;
		}
	}
	for(i=0;i<e;i++) 
		GE[i].weight=0;
}

adjMList::~adjMList()
{

}
void adjMList::CreateMatrix(int v, int &e, RCW r[])
{
	int i,j,k,w;
	for(k=0;k<e;k++)
	{
		i=r[k].row;j=r[k].col;w=r[k].weight;
		GA[i][j]=GA[j][i]=w;
	}
	cout<<"城镇连通图的邻接矩阵为:"<<endl;;
	for(i=0;i<v;i++)
	{
		for(j=0;j<v;j++)
		cout<<setw(4)<<GA[i][j];
		cout<<endl;
	}
}

void adjMList::OutputEdgeSet(edge ge[], int e)
{
	int i,k=0;
	cout<<"{";
	for(i=0; i<=e-2; i++)
	if(ge[i].weight>0)
	{
		k++;
		cout<<'('<<ge[i].fromvex<<','<<ge[i].endvex;
		cout<<','<<ge[i].weight<<") ";
		if(k%5==0) cout<<endl;
	}
	if(e>0&&ge[i].weight>0) 
	{
		cout<<'('<<ge[e-1].fromvex<<','<<ge[e-1].endvex;
		cout<<','<<ge[e-1].weight<<')';
	}
	cout<<'}'<<endl;

}
void adjMList::ChangeEdgeSet(edge GE[], int v, int e)
{
	int i,j,k=0;
	for(i=0; i<v; i++)
	{
		for(j=i+1; j<v; j++)
		{
			if(GA[i][j]!=0 && GA[i][j]!=MaxValue)
			{
				if(k==e) 
				{
					cout<<"数组GE下标越界!\n"; 
					exit(1);
				}
					GE[k].fromvex=i; 
					GE[k].endvex=j;
					GE[k].weight=GA[i][j];
					k++; 
			}
		}
	}
}

void adjMList::Kruskal(edge GE[], int v,int e)
{
	int i,j;
	edge x;
	for(i=1;i<e;i++)                  //用直接插入法对边集进行升序排序
	{
		x.weight=GE[i].weight;
		x.fromvex=GE[i].fromvex;
		x.endvex=GE[i].endvex;
		j=i-1;
		while(x.weight<GE[j].weight&&j>=0)
		{
			GE[j+1].weight=GE[j].weight;
			GE[j+1].fromvex=GE[j].fromvex;
			GE[j+1].endvex=GE[j].endvex;
			j--;
		}
		GE[j+1].weight=x.weight;
		GE[j+1].fromvex=x.fromvex;
		GE[j+1].endvex=x.endvex;
	} 
	int m1, m2;
	int s[MaxV];
	for(i=0;i<v;i++)
		s[i]=0;
		for(i=0;i<v;i++)
		{
			m1=Find(s,GE[i].fromvex);
			m2=Find(s,GE[i].endvex);
			if(m1!=m2)
			{
				s[m1]=m2;
				cout<<'('<<GE[i].fromvex<<','<<GE[i].endvex<<','<<GE[i].weight<<')'<<endl;
			}
		}

}
int adjMList::Find(int s[], int f)
{
	while(s[f]>0)
	f=s[f];
	return(f);
}