graph.h

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

// Graph.h: interface for the Graph class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_GRAPH_H__30EE754C_8883_497C_BF1D_5BB2B5837789__INCLUDED_)
#define AFX_GRAPH_H__30EE754C_8883_497C_BF1D_5BB2B5837789__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include "iostream.h"
const int DefaultSize = 20;	
class MinSpanTree;
class Graph;
			//最小生成树的前视类声明
class MSTEdgeNode
{			//最小生成树边结点的类声明
public:
	friend class MinSpanTree;
    int tail, head;				//两顶点位置
    int cost;					//边上的权值
};

class MinSpanTree {				//最小生成树的类定义
public:
   friend class Graph;
   MinSpanTree ( int sz = DefaultSize-1 ) : MaxSize (sz), n (0),sum(0) 
   { edgeValue = new MSTEdgeNode[MaxSize]; }
   void Insert(MSTEdgeNode e);
private:
   MSTEdgeNode *edgeValue;			//用边值数组表示树
   int MaxSize, n,sum;				//数组的最大元素个数，当前个数以及当前所有边的权值之和
};

		
class Edge 
{
	friend class Graph;
public:
    int dest;//边的另一顶点位置，第一个顶点的位置是隐式的						
    int cost;//边上的权值					
    Edge *link;	//下一条边链指针			
    Edge( ){ }	//构造函数					
    Edge(int D,int C):dest(D),cost(C),link(NULL){ }	//构造函数
};
class Vertex {	
    friend class Edge;
    friend class Graph;
    char name[20];//顶点名称
	char ifo[50];//顶点信息			
    Edge *adj;  //出边表的表头指针
};
class Graph {
private:
    Vertex *NodeTable; //顶点表 
    int NumVertices; //当前顶点个数
    int MaxVertices;  //最大顶点个数
    int NumEdges;	 //当前边数				
	int dist[DefaultSize];//存放从顶点0到其它各顶点的最短路径长度
	int path[DefaultSize];//存放在最短路径上该顶点的前一顶点的顶点号
	int S[DefaultSize];//已求得的在最短路径上的顶点的顶点号
public:
    Graph (int sz);	
	int GetVertexPos ( char *name );//给出名字为name的顶点在图中的位置
    void GetIfo (char *p ); //给出名字为p的顶点的信息  
	void Show();//显示所有顶点及其信息
    void InsertVertex ( char name[],char ifo[]);//插入一个顶点		
    void InsertEdge (int v1,int v2,int weight );//插入边		
    int GetWeight (int v1,int v2);//获得顶点为v1，v2的边的权值
	void Prim(MinSpanTree &T);//获得最小生成树
	void ShortestPath(int v1,int v2);//求得最短路径
};

#endif // !defined(AFX_GRAPH_H__30EE754C_8883_497C_BF1D_5BB2B5837789__INCLUDED_)