ds301.cpp

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

#include <iostream.h>
#include <assert.h>
#include "ds301.h"
#define N 6
#define M 10000

//构造函数
template <class T>
SeqQueue<T>::SeqQueue(int MaxQueSize)
{ 
	MaxSize=MaxQueSize;
	q=new T[MaxSize];
	front=rear=0;
}

//（3） 进队列（插入）
template <class T>
void SeqQueue<T>::EnQueue(const T x)
{ 
	assert(!IsFull());
	q[(rear=(rear+1) % MaxSize)]=x;
}

//（4） 出队列（删除）
template <class T>
void SeqQueue<T>::DeQueue()
{ 
	assert(!IsEmpty());
	front=(front+1) % MaxSize;
}

//（5） 取队列元素
template <class T>
T SeqQueue<T>::Front()
{ 
	assert(!IsEmpty());
	return q[(front+1) % MaxSize];
}

template<class T>  //构造函数
MGraph<T>::MGraph(int mSize, const T& noedg)             
{   
	n=mSize;
	e=0;
	noEdge=noedg;
    a= new T*[n];
    for(int i=0;i<n;i++)
    {	
		a[i]=new T [n];
		for (int j=0;j<n;j++) a[i][j]=noEdge;
		a[i][i]=0;
    }
}

template<class T>   //析构函数
MGraph<T>::~MGraph()
{   
	for(int i=0;i<n;i++) 
		delete []a[i];
    delete []a;
} 

template <class T>     //判边是否存在
bool  MGraph<T>::Exist(int u,int v)const
{  
	if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==noEdge)
		return false;
	return true;
}

template <class T>  //边的插入
ResultCode MGraph<T>::Insert(int u,int v, T& w)
{  
	if(u<0||v<0||u>n-1||v>n-1||u==v) 
		return Failure;
	if(a[u][v]!=noEdge) 
		return Duplicate;
	a[u][v]=w; 
	e++; 
	return Success;
} 

template<class T>
ResultCode MGraph<T>::Remove(int u,int v)
{
	if(u<0||v<0||u>n-1||v>n-1||u==v) 
		return Failure;
	if(a[u][v]==noEdge) 
		return NotPresent;
	a[u][v]=noEdge;
	e--; 
	return Success;
}

//基于邻接矩阵的深度优先搜索的递归算法
template<class T>
void ExtMGraph<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 ExtMGraph<T >::DFS(int v,bool* visited)
{  
	visited[v]=true;
	cout<<" "<<v;
	for(int j=0;j<n;j++)
		if(a[v][j]==1&&visited[j]==false)
			DFS(j,visited);		
}

//基于邻接矩阵的宽度优先搜索的C++程序
template<class T>
void ExtMGraph<T >::BFS()
{
 bool *visited=new bool[n];
 for (int i=0;i<n;i++)
	 visited[i]=false;
for (i=0;i<n;i++)
	if(!visited[i])
		BFS(i,visited);
}

template<class T> //基于邻接矩阵的宽度优先搜索的C++程序私:有BFS函数
void ExtMGraph<T >::BFS(int v, bool* visited) 
{ 
	visited[v]=true;
	cout<<" "<<v;
	for(int j=0;j<n;j++)
		if(a[v][j]==1&&visited[j]==false)
		{
			cout<<" "<<j;
			visited[j]=true;
		}
	for(int l=0;l<n;l++)
		if (a[v][l]==1)
			BFS(l,visited);
}

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)
 //将边<u,v>插入指针a[u]所指示的单链表最前面
{  
	if(u<0||v<0||u>n-1||v>n-1||u==v) return Overflow; 
	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 Overflow;
    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;
} 

//深度优先搜索的递归算法
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);
}

//宽度优先搜索的C++程序
template<class T>
void ExtLGraph<T >::BFS()
{
     bool* visited=new bool[n];
     for(int i=0;i<n;i++) 
         visited[i]=false;
     for (i=0;i<n;i++)
	  if (!visited[i]) 
           BFS(i,visited);
     delete[]visited;
}

template<class T>
void ExtLGraph<T >::BFS(int v, bool* visited) //私有BFS函数
{  
	ENode<T> *w;
	int qSize=N;
	SeqQueue<int> q(qSize);
    visited[v]=true;
    cout<<" "<<v;
    q.EnQueue(v);
	while (! q.IsEmpty())
	{ 
		v=q.Front();
		q.DeQueue();
		for (w=a[v];w;w=w->nextArc)   
        if (!visited[w->adjVex])
        { 
			visited[w->adjVex]=true;
			cout<<" "<<w->adjVex;
			q.EnQueue(w->adjVex);
        }
	}
}

void main()
{
	ExtLGraph<int> lg(6);
	ExtMGraph<int> mg(N,M);	
	int i,u,v,w;
	for (i=0;i<4;i++)  //i<11
	{
		cin>>u>>v>>w;
		if (!lg.Exist(u,v)) lg.Insert(u,v,w);
		if (!mg.Exist(u,v)) mg.Insert(u,v,w);
	}
	cout<<" 基于邻接表的深度优先遍历序列如下:"<<endl;
	lg.DFS();   
	cout<<endl;
	cout<<" 基于邻接表的广度优先遍历序列如下:"<<endl;
	lg.BFS();
	cout<<endl;

	//添加
	cout<<"基于邻接矩阵的深度优先遍历序列如下:"<<endl;
		mg.DFS();
	cout<<endl;
	
    cout<<"基于邻接矩阵的广度优先遍历序列如下:"<<endl;
		mg.BFS();
	cout<<endl;






}