graph.h

数据结构实验课中的所有实验程序

#include "iostream.h"
const int DefaultSize=15;
class MinSpanTree;					
class MSTEdgeNode 
{		                                    //生成树边结点类定义
	friend class MinSpanTree;
public: 
	int tail, head;			                //生成树各边的两顶点
    int cost;	                            //生成树各边的代价
};
class MinSpanTree
{                                            //生成树的类定义
	//friend class Graph;
public:
	MinSpanTree (int sz=DefaultSize-1):MaxSize(sz),nowedge(0)
	{ 
		edgevalue=new MSTEdgeNode[MaxSize]; 
	}
    void Insert(MSTEdgeNode &temp)//向生成树边值数组内存放
	{
	   edgevalue[nowedge].tail = temp.tail;  
	   edgevalue[nowedge].head = temp.head;  
	   edgevalue[nowedge].cost = temp.cost;
	   max=max+temp.cost;	   
	   nowedge++;
	}
public:
    MSTEdgeNode *edgevalue;             	 //边值数组	
    int MaxSize, nowedge,max;                    //最大边数,当前边数
};		

class Edge 
{
	public:
    int dest;						
    int cost;					
    Edge *link;				
    Edge ( ) { }						
    Edge (int D,int C):dest(D),cost(C),link(NULL){ }	
    int operator!=( const Edge &E )const{return dest != E.dest;} 
};
class Vertex 
{	
    friend class Edge;
    friend class Graph;
    char data[50];                                     //顶点名字	
	char info[500];
    Edge *adj;                                  //出边表的表头指针
};
class Graph
{
	friend class MinSpanTree;
	private:
		Vertex *NodeTable;
		int NumVertices;
		int MaxNumVertices;
		int NumEdges;
		int dist[DefaultSize];			
        int path[DefaultSize];
    	int S[DefaultSize];	
		int GetVertexPos(char vertex[]);
	public:
		Graph(){};
		Graph(int sz);
		~Graph();
		void load();
		int getNE(){return NumEdges;}
		int GraphEmpty()const{return NumVertices==0;}
		int GraphFull()const{return NumVertices==MaxNumVertices;}
		int NumverOfVertices(){return NumVertices;}
		int NumverOfEdges(){return NumEdges;}
		char *GetValue(int i)
		{
			return i>=0&&i<NumVertices?NodeTable[i].data:NULL;
		}
		void InsertVertex (const char vertex[]);
		void RemoveVertex(int v);
		void InsertEdge(const int v1, const int v2, const int weight);
		void RemoveEdge(int v1,int v2);
	    int GetWeight(int v1,int v2);
		int GetFirstNeighbor(int v);
		int GetNextNeighbor(int v1,int v2);
		void Components(); 
		void DFS();
		void DFS (const int v, int visited []);
        void Prim(MinSpanTree &T);
		void InsertInfo(const char inf[]);
		void SearchInfo(char name[]);
		void ShortestPath(int n,int v);
		void SP(char n1[],char n2[]);
		void Modify();
};