ds301.h

图的深度遍历与广度遍历的链接矩阵和链接表实现

enum ResultCode{Success,NotPresent,Duplicate,Overflow,Failure,Underflow};

//程序9.1 Graph类
template <class T>
class Graph
{
 public:	
    virtual ResultCode Insert(int u,int v, T& w)=0;
    virtual ResultCode Remove(int u,int v)=0;
    virtual bool Exist(int u,int v)const=0;
    virtual int Vertices()const {return n;}

 protected:
    int n,e;
}; 

//程序9.2 MGraph类
template<class T>
class MGraph:public Graph<T>
{
public:
    MGraph(int mSize,const T& noedg);
    ~MGraph();
    ResultCode Insert(int u,int v, T& w);
    ResultCode Remove(int u,int v); 
    bool Exist(int u,int v)const;

protected:
   T **a;     //动态二维数组
   T noEdge;  //两结点间无边时的值(0或无穷大)
}; 

//ExtMGraph类
template <class T>
class ExtMGraph: public MGraph<T>
{
public:
	ExtMGraph(int mSize,int noedg):MGraph<T>(mSize,noedg){}; //调用父类的构造函数
    void DFS();
    void BFS();

private:
    void DFS(int v,bool* visited);
    void BFS(int v,bool* visited);
};


//程序9.5 ENode类	
template<class T >
struct ENode //邻接表的单链表结点类
{ 
	ENode()  { nextArc=NULL; }
	ENode(int vertex,T weight,ENode *next)
	{    
		adjVex=vertex; 
		w=weight; 
		nextArc=next;
	}
	int adjVex;
	T w;
	ENode<T>* nextArc;
};

//程序9.6 LGraph类
template<class T>
class LGraph: public Graph<T>  //图的邻接表类声明
{
public:
    LGraph(int mSize);                
    ~LGraph();
    ResultCode Insert(int u,int v, T& w) ;
    ResultCode Remove(int u,int v) ;
    bool Exist(int u,int v)const ;

protected:
   ENode<T> **a;
};

//程序9.9 ExtLGraph类
template <class T>
class ExtLGraph: public LGraph<T>
{
public:
	ExtLGraph(int mSize):LGraph<T>(mSize){};   //调用父类的构造函数
    void DFS();
    void BFS();

private:
    void DFS(int v,bool* visited);
    void BFS(int v,bool* visited);
};

//程序3-5 队列的C++类
template <class T>
class Queue	
{ 
public:
	Queue(){};
	~Queue(){};	
	virtual void EnQueue(const T x)=0; 
	virtual void DeQueue()=0;
	virtual  T Front()=0;	  
	virtual bool IsEmpty() const=0;	  
	virtual bool IsFull() const=0;	  
};

//程序3-6循环队列
template <class T>
class SeqQueue:public Queue<T>
{ 
public:
	SeqQueue(int MaxQueSize);
	~SeqQueue(){ delete []q;}
	void EnQueue(const T x);
	void DeQueue();
	T Front();
	bool IsEmpty() const{ return front==rear;}
	bool IsFull() const{ return (rear+1) % MaxSize==front; }
private:
	int front,rear;
	int MaxSize;
	T *q;
};