graph.h

校园导游图

#pragma once

#define MaxNumEdges   38				//最大边数
const int MaxNumVertices=19;				//最大顶点数
#define MAXINT 2000                      //权值的最大值
#define VERTICES 19						//顶点总数


class CGraph
{
public:
	CGraph( const int sz=MaxNumEdges );					//构造函数
	~CGraph() {};
	int GetValue ( const int i );						//取顶点i的值, i不合理则返回空
	int GetWeight ( const int v1, const int v2 );	//给出以顶点v1和v2为两端点的边上的权值
	int GetFirstNeighbor ( const int v );				//给出顶点位置为v的第一个邻接顶点的位置
	int GetNextNeighbor ( const int v1, const int v2 );	//给出顶点位置v1的某邻接顶点v2的下一个邻接顶点

	void InsertVertex(int);
	void InsertEdge ( const int, const int, int );	//插入一条边(v1, v2), 该边上的权值为weight
	int* BestPath(int, int, int&, int&);                  //输出最短路径

	void AllLengths();
//	int* Prim(int& count);
	int* DFS(int& count);
	void DFS(const int v, int visited[], int &count, int*);
private:
	CString strAddress,strTemp,strOutput;       //为输出所求路的径信息而设;
	int Edge[MaxNumVertices][MaxNumVertices];	//邻接矩阵
	int dist[MaxNumVertices][MaxNumVertices];	//存放从顶点0到其它各顶点的最短路径长度
	int path[MaxNumVertices][MaxNumVertices];	//存放在最短路径上该顶点的前一顶点的顶点号
};