lgraph.cpp

遍历邻接表以及执行邻接矩阵布尔调整是数据结构里图的经典算法。

#include <iostream.h>

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


//程序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.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* 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 ;
    void Create();
    void Traversal();
protected:
   ENode<T>** a;
};
 
template<class T>
void LGraph<T >::Create()   //       >F---->B<----A
{  int w=1;                 //     /  ^     |\    ^
   Insert(0,1,w);           //   E    |     | \   |
   Insert(1,2,w);           //     \  |     v  \  |
   Insert(1,3,w);           //       >G---->D---->C
   Insert(3,2,w);           //
   Insert(3,0,w);           //
   Insert(2,0,w);           //
   Insert(5,1,w);           //
   Insert(6,3,w);
   Insert(6,5,w);
   Insert(4,5,w);
   Insert(4,6,w);
}

//遍历邻接表
template<class T>
void LGraph<T >::Traversal()
{  ENode<T>*p;
   for(int i=0;i<n;i++)
   {  p=a[i];
      cout<<i;
      while(p)
      { cout<<"->"<<p->adjVex;
        p=p->nextArc;
      }
      cout<<endl;
   }
}

//程序9.7 构造函数和析构函数
template<class T>
LGraph<T >::LGraph(int mSize)
{                
n=mSize;e=0;
a=new ENode<T>* [n];
for (int i=0;i<n;i++) a[i]=NULL;
}
template<class T>
LGraph<T >::~LGraph()
{	
ENode<T>* p,*q;
for(int i=0;i<n;i++){
	p=a[i];q=p;
	while (p) {
		p=p->nextArc;delete q;q=p;
	}
}
delete[] a;
 }
 
template<class T>
bool LGraph<T >::Exist(int u,int v)const
{
	if(u<0||v<0||u>n-1||v>n-1||u==v) return false;
   ENode<T>* p=a[u];
	while (p&& p->adjVex!=v) p=p->nextArc;
	if (!p) return false;
	else return true;
}

template<class T>
ResultCode LGraph<T >::Insert(int u,int v, T& w) 
{	
	  if(u<0||v<0||u>n-1||v>n-1||u==v) return Failure;
    if(Exist(u,v)) return Duplicate;
 	  ENode<T>* p=new ENode<T>(v,w,a[u]);
    a[u]=p; e++;
    return Success;
}

template<class T>
ResultCode LGraph<T >::Remove(int u,int v)
{
	if(u<0||v<0||u>n-1||v>n-1||u==v) return Failure;
   ENode<T>* p=a[u],*q=NULL;
	while (p&& p->adjVex!=v){
		q=p;p=p->nextArc;
	}
	if (!p) return NotPresent;
	if (q) q->nextArc=p->nextArc;
	else a[u]=p->nextArc;
	delete p;  e--;
	return Success;
}
 
//程序9.9 ExtLGraph类
struct EDGE
{ int from,to;
};

template <class T>
class ExtLGraph: public LGraph<T>
{
public:
  ExtLGraph(int mSize):LGraph<T>(mSize){}             //调用父类的构造函数
	void DFS();
  void DFS1();                   //DFS的非递归算法
	void BFS();
  void DFS2(int parent[]);       //利用DFS算法求DFS生成树/生成森林
  void DFS3(int ed[],int &k1,struct EDGE edge[],int &k2);
private:
	void DFS(int v,bool* visited);                   
	void DFS1(int v,bool* visited); //DFS的非递归算法
	void BFS(int v,bool* visited);                   
  void DFS2(int v,bool visited[],int parent[]);   
  void DFS3(int v,bool visited[],int ed[],int &k1,struct EDGE edge[],int &k2);
};                                                   
 

//程序9.10  DFS算法
template<class T>
void ExtLGraph<T >::DFS()
{
  bool* visited=new bool [n];
  for(int i=0;i<n;i++) visited[i]=false;
  for (i=0;i<n;i++)
    if (!visited[i]) DFS(i,visited);
  delete[]visited;
}

template<class T>
void ExtLGraph<T >::DFS(int v,bool* visited)
{
    visited[v]=true;cout<<" "<<v;
    for (ENode<T> *w=a[v]; w; w=w->nextArc)
       if (!visited[w->adjVex]) DFS(w->adjVex,visited);
}
 
template<class T>
void ExtLGraph<T >::DFS1()                  //DFS的非递归算法
{
  bool* visited=new bool [n];
  for(int i=0;i<n;i++) visited[i]=false;
  for (i=0;i<n;i++)
    if (!visited[i]) DFS1(i,visited);
  delete[]visited;
}

template<class T>
void ExtLGraph<T >::DFS1(int v,bool* visited)
{   ENode<T> *p,*stack[10];
    int top=-1;

    cout<<" "<<v<<' '; visited[v]=true;
    p=a[v];
    while(top>-1||p)
    {  while(p)
          if(visited[p->adjVex]) p=p->nextArc;
          else
          {  cout<<p->adjVex<<' ';  
             visited[p->adjVex]=true;
             stack[++top]=p;
             p=a[p->adjVex];
          }
       if(top>-1)
       {  p=stack[top--];
          p=p->nextArc;
       }
    }
    cout<<endl;
}

//程序9.11 BFS算法
template<class T>
void ExtLGraph<T >::BFS(int v, bool* visited)
{
   SeqQueue<int> q(QSize);
   visited[v]=true; cout<<" "<<v;
   q.EnQueue(v);
   while (! q.IsEmpty())
   { q.Front(v);q. DeQueue();
     for (ENode<T> *w=a[v];w;w=w->nextArc)   
        if (!visited[w->adjVex])
        { visited[w->adjVex]=true;cout<<" "<< w->adjVex;
	        q.EnQueue(w->adjVex);
       }
   }
}

template <class T >
void  ExtLGraph<T>::DFS2(int parent[])     //利用DFS算法求DFS生成树/生成森林
{ bool *visited;
 
  visited=new bool[n];                         //       F     B<----A
  for(int i=0; i<n; i++)                       //       ^     |
  { visited[i]=false; parent[i]=-1;            //  E    |     |
  }                                            //    \  |     v
  for(i=0; i<n; i++)                           //      ->G    D---->C
    if(!visited[i]) DFS2(i,visited,parent);    //parent[]数组是森林的双亲表示法，如果parent[i]=-1，说明顶点i是子树的根
  delete []visited;
}

template <class T >
void ExtLGraph<T>::DFS2(int v,bool visited[],int parent[])
{ ENode<T> *w;
  visited[v]=true;
  for(w=a[v]; w; w=w->nextArc)
    if(!visited[w->adjVex])
    { DFS2(w->adjVex,visited,parent);
      parent[w->adjVex]=v;               //v---->w-adjVex,即在生成树中，顶点w-adjVex的父结点是v
    }
}

template <class T> 
void ExtLGraph<T>::DFS3(int ed[],int &k1,struct EDGE edge[],int &k2)  //利用DFS算法求DFS生成树/生成森林的另一种方法
{ bool *visited=new bool [n]; 
  int m;
  
  for (int i=0;i<n;i++) visited[i]=false;
  for (i=0;i<n;i++)
    if (!visited[i])
    { m=k2;
      DFS3(i,visited,ed,k1,edge,k2); 
      if(m==k2)                              //edge[i].from和edge[i].to是一棵子树边的起点和终点
      { edge[k2].from=i;  edge[k2++].to=-1;  //-1表示森林中的子树就一个顶点，没有边
        ed[k1++]=k2;                         //ed数组存储森林中每棵子树在边数组edge[]中的上界，
      }                                      //比如上图：ed[0]=3,ed[1]=5，说明edge[0]-edge[2]存储的是一棵子树的边
      else ed[k1++]=k2;                      //edge[3]-edge[4]是另一棵子树的边
    }
  delete  []visited;
}

template <class T >    
void ExtLGraph<T>::DFS3(int v,bool visited[],int ed[],int &k1,struct EDGE edge[],int &k2)
{ ENode<T> *w;   
  visited[v]=true; 
  for (w=a[v]; w; w=w->nextArc)
   if (!visited[w->adjVex])
   { edge[k2].from=v;  edge[k2++].to=w->adjVex; 
     DFS3(w->adjVex,visited,ed,k1,edge,k2); 
   }
}

#define N 7
void main()
{  
   ExtLGraph<int> g(N);
   int parent[N];
   struct EDGE edge[N];
   int ed[N];
   int k1=0,k2=0;
   
   g.Create();
   cout<<"遍历邻接表"<<endl;
   g.Traversal();   cout<<endl;

   cout<<"DFS图(非递归)"<<endl;
   g.DFS1();
   
   cout<<"DFS生成树/生成森林(方法一)"<<endl;
   g.DFS2(parent);
   cout<<"  ";
   for(int i=0;i<N;i++) cout<<i<<"  ";
   cout<<endl;
   for(i=0;i<N;i++) cout<<parent[i]<<"  ";
   cout<<endl;

   ed[0]=0;
   cout<<endl<<"DFS生成树/生成森林(方法二)"<<endl;
   g.DFS3(ed,k1,edge,k2);
   cout<<"ed[]="<<endl;
   for(i=0;i<k1;i++) cout<<ed[i]<<" ";
   cout<<endl;
   cout<<"edge[]="<<endl;
   for(i=0;i<k2;i++)
   { cout<<edge[i].from<<"  "<<edge[i].to<<endl;
   }
}