graph.cpp

校园导游图

#include "StdAfx.h"
#include "Graph.h"

//图的邻接矩阵表示,任意两个顶点最短路径算法

#include "assert.h"
#include "queue.h"

#include "Sqlist.h"
//#include "MinSpanTree.h"

extern CSqlist VerticesList;			//顶点表

CGraph::CGraph ( int sz ){
	//构造函数
	for ( int i=0; i<sz; i++ )					//邻接矩阵初始化
		for ( int j=0; j<sz; j++ ) Edge[i][j] = MAXINT;
}


int CGraph::GetValue ( const int i )			//取顶点i的值, i不合理则返回空
{ return VerticesList.Get(i); }	

int CGraph::GetWeight ( const int v1, const int v2 ) 
{
	//给出以顶点v1和v2为两端点的边上的权值
	if ( v1 != -1 && v2 != -1 ) return Edge[v1][v2];
	else return NULL;							//带权图中权值为0, 表示无权值
}

int CGraph::GetFirstNeighbor ( const int v ) {
	//给出顶点位置为v的第一个邻接顶点的位置, 如果找不到, 则函数返回-1。
	if ( v != -1 ) {
		for ( int col=0; col<VERTICES; col++ ) if ( Edge[v][col] > 0 && Edge[v][col] < MAXINT ) return col;
	}
	return -1;
}

int CGraph::GetNextNeighbor ( const int v1, const int v2 ) {
	//给出顶点v1的某邻接顶点v2的下一个邻接顶点
	if ( v1 != -1 && v2 != -1 )
	{
		for ( int col=v2+1; col<VERTICES; col++ )
			if ( Edge[v1][col] > 0 && Edge[v1][col] < MAXINT ) return col;
	}
	return -1;
}

void CGraph::InsertVertex ( int vertex )		//插入一个顶点vertex, 该顶点没有入边
{
	if(VerticesList.Length()<=MaxNumVertices)
		VerticesList.Insert ( vertex, VerticesList.Length() );		
};

void CGraph:: InsertEdge ( const int v1, const int v2, int weight )	//插入一条边(v1, v2), 该边上的权值为weight
{
	Edge[v1][v2]=weight;
};

/*int *CGraph::Prim(int& count){
	MinSpanTree T;
	int NumVertices = VERTICES;
    int * lowcost = new int [NumVertices];
    int * nearvex = new int [NumVertices];
    int *iPointIndex = new int [VERTICES+1];
    count = 0;
       for(int i=1; i<NumVertices;i++){
             lowcost[i]=Edge[0][i];
             nearvex[i]=0;
	   }
          nearvex[0]=-1;
		  iPointIndex[count++]=0;
          MSTEdgeNode e;
   for( i=1; i<NumVertices;i++){
    int min=MAXINT;int v=0;
    for(int j=0; j<NumVertices;j++)
         if(nearvex[j]!=-1&&lowcost[j]<min){v=j;min=lowcost[j];}
		 iPointIndex[count++]=v;
		 if(v){
			 e.tail=nearvex[v];
	         e.head=v;
	         e.cost=lowcost[v];
	         T.Inser(e);
	         nearvex[v]=-1;
         for(int j=1; j<NumVertices;j++)
	    if(nearvex[j]!=-1&&Edge[v][j]<lowcost[j])
		{lowcost[j]=Edge[v][j];nearvex[j]=v;}
		 }
   }
	return iPointIndex;
}
*/

 
int *CGraph::DFS(int& count) //对连通图进行深度优先搜索的主过程
{				
	int *iPointIndex = new int [VERTICES+1];
	int *visited	 = new int [VERTICES];			//创建辅助数组
	count			 = 0;
	for (int i=0; i<VERTICES; i++)
	{
		visited [i] = 0;							//辅助数组初始化
	}

	for (i=0; i<VERTICES; i++) 
	{
		if (!visited[i])  
			DFS (i ,visited, count, iPointIndex);	//从顶点0开始深度优先搜索
	}

	iPointIndex[count++] =18;
	count=19;

	return iPointIndex;
}

void CGraph::DFS( const int v, int visited [ ], int& count, int *iPointIndex) 
{
	//从顶点位置v出发, 以深度优先的次序访问所有可读入的尚未访问过的顶点。算法中用到一个辅助数组
	// visited, 对已访问过的顶点作访问标记。
	
	//访问该顶点的数据
	iPointIndex[count++] = GetValue(v);
	visited[v] = 1;									//访问标志改为已访问过
	int w = GetFirstNeighbor(v);					//找顶点v的第一个邻接顶点w
	while ( w != -1 )								//有邻接顶点
	{				
		if ( !visited[w] )
		{	
			DFS(w, visited, count, iPointIndex);	//若未访问过, 从w递归访问
		}
		w = GetNextNeighbor( v,w );				//找顶点v的下一个邻接顶点
	}
}

 
void CGraph:: AllLengths ( )
{
	//Edge[n][n]是一个具有n个顶点的图的邻接矩阵。a[i][j]是顶点i和j之间的最短路径长度。path[i][j]是相应路
	//径上顶点j的前一顶点的顶点号, 在求最短路径时图的类定义中要修改path为path[NumVertices][NumVertices]。
	for ( int i=0; i<VERTICES; i++ )
	{
		for ( int j=0; j<VERTICES; j++ ) 	//矩阵a与path初始化
		{						
			if (i!=j) 
				dist[i][j] = Edge[i][j];
			else 
				dist[i][j]=0;

			if ( i != j && dist[i][j] < MAXINT ) 
				path[i][j] = i;							// 有路径
			else 
				path[i][j] =-1;							// i到j无路径
		}
	}

	for ( int k=0; k<VERTICES; k++ )	//产生a(k)及相应的path(k)
	{
		for ( i=0; i<VERTICES; i++ )
		{
			if (path[i][k] >= 0)
			{
				for ( int j=0; j<VERTICES; j++ )
				{
					if( path[k][j]>=0 && dist[i][k] + dist[k][j] < dist[i][j] )
					{
						dist[i][j] = dist[i][k] + dist[k][j];
						path[i][j] = path[k][j];		//缩短路径长度, 绕过k到j
					}
				}
			}
		}
	}
}

int *CGraph::BestPath(int start,int end, int &verNum, int& distance)
{
	int* iPointIndex = NULL; 
	CWordArray wArray; 
	wArray.RemoveAll();
	verNum = 0;
	for (int index= path[start][end]; index!=start;)
	{
		if (start != end)
		{
			if(Edge[index][path[start][index]]>0&&Edge[index][path[start][index]]<MAXINT)
			{
				wArray.Add(index);
			    index= path[start][index];
			}
			else
			{
				wArray.Add(path[start][index]);
				wArray.Add(index);
			    index= path[start][index];
			}
		}
		else
			break;
	
	}
	int count = wArray.GetSize();
	iPointIndex = new int[count+3];
	iPointIndex[verNum++] = start;

	for (int i= count; i>0; i--)
	{
		iPointIndex[verNum++] = wArray.GetAt(i-1);
	}

	iPointIndex[verNum++] = end;

	distance = dist[start][end];

	return iPointIndex;
}