graph.cpp

用VC++编写的学校地图信息系统

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

#include "stdafx.h"
#include "Graph.h"
#include "fstream.h"
#include "stdlib.h"
#include "string.h"
#define MAXNUM 10000

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

void MinSpanTree::Insert(MSTEdgeNode e)//向生成树边值数组内存放结点
{
	   edgeValue[n].tail =e.tail;  
	   edgeValue[n].head =e.head;  
	   edgeValue[n].cost =e.cost;
	   sum=sum+e.cost;	   
	   n++;
}

Graph::Graph (int sz=DefaultSize) :NumVertices (0),MaxVertices(sz),NumEdges (0)
{
	fstream f1;
	f1.open("graph.dat",ios::in);//打开数据文件
	if(!f1)
	{
		cout<<"不能打开文件!"<<endl;
		abort();
	}
    int n, e,v1,v2,weight; char name[20],ifo[50],beg[20],end[20]; 
   
    NodeTable =new Vertex[MaxVertices];//创建顶点表
    f1>>n>>e;			   //读取顶点和边的个数
    for ( int i = 0; i < n; i++)   //读取各顶点信息
	{
		f1>>name>>ifo;
		InsertVertex (name,ifo);//向图中插入顶点 
	}
    for ( i =0; i <e; i++) 
	{         //逐条边读取
       f1>>beg>>end>>weight;
	   v1=GetVertexPos(beg);
	   v2=GetVertexPos(end);
       InsertEdge (v1,v2,weight);//将无向图看作是双向的有向图将边插入图中
       InsertEdge (v2,v1,weight);
    }
	f1.close();//关闭数据文件
}	    

int Graph::GetVertexPos ( char *name) 
{
//根据名称name查找该顶点在邻接表中的位置
    for ( int i =0; i <NumVertices; i++ )
    if (strcmp(NodeTable[i].name,name)==0) return i;
    return -1;
} 
void Graph::GetIfo (char *p )//显示名称为p的景点信息
{
	for(int i=0;i<NumVertices;i++)
		if(strcmp(NodeTable[i].name,p)==0)
		{cout<<NodeTable[i].ifo<<endl;return;}
}
void Graph::Show()//显示所有景点名称及其信息
{
	for(int i=0;i<NumVertices;i++)
	{
		cout<<NodeTable[i].name<<"   ";
		if((i+1)%5==0)cout<<endl;
	}
	if(NumVertices%5!=0) cout<<endl; 
}
int Graph::GetWeight (int v1, int v2)
 {
//取两端点为 v1 和 v2 的边上的权值
	if(v1==v2) return 0;
    else if ( v1 != -1 && v2 != -1 ) 
	{
       Edge *p=NodeTable[v1].adj;
       while ( p != NULL ) 
	   {
	       if ( p->dest == v2 ) return p->cost;
           else p=p->link;
       }
    }
    return MAXNUM;
}
 
void Graph::InsertVertex ( char name[],char ifo[])
{//向邻接表中插入名称为name，信息为ifo的顶点
	strcpy(NodeTable[NumVertices].name,name);
	strcpy(NodeTable[NumVertices].ifo,ifo);
	NodeTable[NumVertices].adj=NULL;
	NumVertices++;
}
 
void Graph::InsertEdge ( int v1, int v2, int weight )
{//向邻接表中插入边
	Edge *p=new Edge;
	p->dest=v2;
	p->cost=weight;
	p->link=NodeTable[v1].adj;
	NodeTable[v1].adj=p;
	NumEdges++;
}
void Graph::Prim(MinSpanTree &T)
{//求最小生成树
	int *lowcost=new int[NumVertices];//创建辅助数组
	int *nearvex=new int[NumVertices];//创建辅助数组TV
	Edge *p=NodeTable[0].adj;
	for(int i=1;i<NumVertices;i++)
	{
		lowcost[i]=GetWeight(0,i);nearvex[i]=0;
	}
	nearvex[0]=-1;//顶点0加到生成树顶点集合，用－1表示
	MSTEdgeNode e;
	for(i=1;i<NumVertices;i++)//循环n－1次，加入n－1条边
	{
		int min=MAXNUM;int v=0;//求生成树外顶点到生成树内顶点具有最小权值的边
		for(int j=0;j<NumVertices;j++)//确定当前具有最小权值的边及顶点位置
			if(nearvex[j]!=-1&&lowcost[j]<min){v=j;min=lowcost[j];}
		if(v)                    //v＝＝0表示再也找不到要求的顶点了
		{ 
			e.tail=nearvex[v];
			e.head=v;
			e.cost=lowcost[v];
			T.Insert(e);
			nearvex[v]=-1;          //加入生成树顶点集合
			for(j=1;j<NumVertices;j++)
				if(nearvex[j]!=-1&&GetWeight(v,j)<lowcost[j])
				{lowcost[j]=GetWeight(v,j);nearvex[j]=v;}//修改
		}
	}
	cout<<"最短线路总长为："<<T.sum<<endl;//显示最短线路长度及其路径
	cout<<"各边为："<<endl;
	for (i=0;i<T.n;i++)
	cout<<NodeTable[T.edgeValue[i].tail].name<<"\t"<<NodeTable[T.edgeValue[i].head].name<<endl;
}
void Graph::ShortestPath(int v1,int v2)
{//求最短路径
	for(int i=0;i<NumVertices;i++) 
	{				
        dist[i]=GetWeight(v2,i);     //dist数组初始化
        S[i]=0;					
        if(i!=v2&&dist[i]<MAXNUM) path[i] = v2;
        else path[i]=-1;	        //path数组初始化	
    }    
	S[v2] = 1;   dist[v2] = 0;	//终点v2加入顶点集合
    //选择当前不在集合S中具有最短路径的顶点u
    for(i=0;i<NumVertices-1;i++) 
	{			
        int min=MAXNUM; int u=v2;
        for(int j=0;j<NumVertices;j++)		
	    if (!S[j]&&dist[j]<min) 
   	    {u=j;min=dist[j];}
        S[u] = 1;	                //将顶点u加入集合S
        for(int w=0;w<NumVertices;w++)    //修改 
	    if(!S[w]&&GetWeight(u,w)<MAXNUM && dist[u] +GetWeight(u,w)<dist[w]) 
		{
	       dist[w]=dist[u]+GetWeight(u,w); 
	       path[w] = u;
		}   
	}
	int v=v1;     //显示从源点到终点的最短路径
	cout<<"最短路径长度为："<<dist[v1]<<endl;
	cout<<"最短路径为："<<endl;
	while(v!=v2)
	{
	   cout<<NodeTable[v].name<<"→";
	   v=path[v];
	}
	cout<<NodeTable[v2].name<<endl;
}