graph.h

数据结构中图的相关算法的 应用与分析

#ifndef gjrjgejggorgj
#define gjrjgejggorgj
#define UNVISITED 0
#define VISITED 1
#define INFINITY 9999999
#include"Edge.h"
class Graph
{
public:
	int numVertex;	//图的顶点的个数
	int numEdge;    //图的边的个数
	int *Mark;      //Mark指针指向保存有图的顶点的标志位的数组,标志位用来标记某顶点是否被访问过
	int *Indegree;  //Indegree指针指向保存有图的顶点的入度的数组	
	
	Graph(int numVert)               //构造函数
	{
		numVertex=numVert;           //确定图的顶点的个数
		numEdge=0;                   //确定图的边数的个数
		Indegree=new int[numVertex]; //为保存图的顶点的入度申请数组,Indegree为数组指针
		Mark=new int[numVertex];     //为图的顶点的标志位申请数组,Mark为数组指针
		for(int i=0;i<numVertex;i++) //确定图的顶点的标志位和入度,即所有顶点的标志位初始化为未被访问过,入度初始化为0
		{
			Mark[i]=UNVISITED;
			Indegree[i]=0;
		}
	}

	~Graph()                         //析构函数
	{
		delete [] Mark;              //释放Mark数组
		delete [] Indegree;          //释放Indegree数组
	}
	virtual Edge FirstEdge(int oneVertex)=0;  //返回与顶点oneVertex相关联的第一条边
    virtual Edge NextEdge(Edge preEdge)=0;    //返回与边PreEdge有相同关联顶点oneVertex的下一条边

    int VerticesNum()              //返回图的顶点个数
	{
		return numVertex;
	}

    int EdgesNum()                 //返回图的边数
	{
		return numEdge;
	}
    
    bool IsEdge(Edge oneEdge)      //如果oneEdge是边则返回TRUE，否则返回FALSE
	{
		if(oneEdge.weight>0&&oneEdge.weight<INFINITY&&oneEdge.to>=0) 
		{
			return true;
		}
		else 
		{
			return false;
		}
	}

	int FromVertex(Edge oneEdge)   //返回边oneEdge的始点
	{
		return oneEdge.from;
	}

	int ToVertex(Edge oneEdge)     //返回边oneEdge的终点
	{
		return oneEdge.to;
	}

	int Weight(Edge oneEdge)	   //返回边oneEdge的权
	{
		return oneEdge.weight;
	}
	virtual void setEdge(int from,int to,int weight)=0;
	virtual void delEdge(int from,int to)=0;
};
#endif