0801.cpp

功能：构造图

#include <iostream.h>
#include <malloc.h>
#include <stdlib.h>
#define size 30
#define MAXSIZE 20

//图的邻接表示 
struct edge										//顶点的边
{
	bool mark;									//访问标记
	int no;										//顶点编号
	edge * link;								//指向边表的后继
};
struct node										//图顶点
{
	bool mark;									//访问标记
	char letter;								//顶点数据域
	edge * out;									//指向边表的指针
};
struct Stack									//整型栈
{
	int top;
	int elem[MAXSIZE];	
};
struct Queue									//队列
{
	int count,front;							//计数器和队头指针
	int elem[MAXSIZE];							//队列中元素为int型
}queue;

void GraphInput (node * nodelist,int n);
void DeepFSearch(node* nodelist,int n);			//图的深度优先遍历（邻接表存储结构）
void WideFSearch(node* nodelist,int n);			//图的广度优先遍历（邻接表存储结构）		

void CreatQueue(Queue &queue);
bool FullQueue(Queue &queue);
void EnQueue(int elem,Queue &queue);
void DeQueue(int &em,Queue &queue);				//elem纪录出队元素值
void PrintQueue(Queue &queue);

void Creat(Stack &stack);
bool Full(Stack stack);
bool Empty(Stack stack);
void Push(Stack &stack,int elem);
void Pop(Stack &stack,int & em);
char Top(Stack stack);
void Print(Stack stack);

void CreatQueue(Queue &queue)
{
	queue.count=0;
	queue.front=0;									//设初始时队头指向第0个位置
}
bool FullQueue(Queue &queue)
{
	return queue.count==MAXSIZE;
}

void EnQueue(int elem,Queue &queue)
{
	int rear;						
	if(!FullQueue(queue))
	{
		rear=(queue.front+queue.count)%MAXSIZE;		//指向下一入队位置
		queue.elem[rear]=elem;
		queue.count++;
	}
	else cout<<"上溢!";
}

void DeQueue(int &em,Queue &queue)					//em纪录出队元素值
{
	if (queue.count==0){cout<<"下溢!";exit(-1);}
	em=queue.elem[queue.front];
	queue.front=(queue.front+1)%MAXSIZE;
	queue.count--;
}

void PrintQueue(Queue &queue)
{
	int p=queue.front;
	cout<<"队列为:";
	for(int i=1;i<=queue.count;i++)
	{
		cout<<queue.elem[p]<<",";
		p=(p+1)%MAXSIZE;
	}
	cout<<endl;
}

void Creat(Stack &stack)
{
	stack.top=-1;									//栈初始化	
}

bool Full(Stack stack)
{    return stack.top==MAXSIZE-1; }

bool Empty(Stack stack)
{    return stack.top==-1; }

void Push(Stack &stack,int elem)					//入栈
{
	if(stack.top==MAXSIZE-1)	{cout<<"Stack上溢！";}
	else{
			stack.top++; 
			stack.elem[stack.top]=elem;
		}
}
void Pop(Stack &stack, int & em)					//出栈,出栈元素纪录于em
{
	if(stack.top==-1)	{cout<<"Stack下溢！";}
	else{
			em=stack.elem[stack.top];
			stack.top--; 	
		}
}
void Print(Stack stack)								//打印
{
	int p=stack.top;
	cout<<"从栈顶到栈底依次是："<<endl;
	while(p!=-1)
		{ cout<<stack.elem[p]<<"  ";p--;}
	cout<<endl;
}
char Top(Stack stack)
{
	return stack.elem[stack.top];
}

int main ()
{
	int n;
	cout<<"请输入图顶点数:";
	cin>>n;
	node nodeL[10];
	node * nodelist=nodeL;

	GraphInput (nodelist,n);						//构造图的邻接表
	DeepFSearch(nodelist,n);						//图的深度优先遍历
	WideFSearch(nodelist,n);						//图的广度优先遍历
}
//构造图的邻接表
void GraphInput (node * nodelist,int n)				
{
	int i,m;
	edge *q,*p;
	for (i=0;i<n;i++)								//以下输入顶点数据域
	{
		cout<<"请输入顶点"<<i+1<<"的数据域"<<endl;
		cin>>nodelist[i].letter;
		nodelist[i].mark=false;						//初始化为未访问
		nodelist[i].out=0;							//边表初始置空	
	}
	
	for (i=0;i<n;i++)								//以下设置顶点的边表
	{
		cout<<"请输入与第"<<i+1<<"个顶点关联的边数"<<endl;
		cin>>m;
		if (m)
		{
			nodelist[i].out=(edge *)malloc(sizeof(edge));
			p=nodelist[i].out;
			cout<<"请输入与第"<<i+1<<"个顶点的第1条边"<<endl;
			cin>>p->no;
			p->mark=false;
			p->link=0;
			
			for (int j=1;j<m;j++)					//输入剩下的m-1条边
			{
				q = (edge *)malloc(sizeof(edge));
				cout<<"请输入与第"<<i+1<<"个顶点的第"<<j+1<<"条边"<<endl;
				cin>>q->no;
				q->mark=false;
				q->link=0;
				p->link=q;
				p=q;								//后移p		
			}		
		}
	}
}
//图的深度优先遍历（邻接表存储结构）
void DeepFSearch(node* nodelist,int n)				
{
	cout<<endl<<"以下进行图的深度优先遍历"<<endl;
	int i,k,p;
	bool notfinish;
	Stack stack ;
	Creat(stack);
	edge * next[size];								//next[i]是每个顶点边表要检查的下一条边
	
	for (i=0;i<n;i++)   next[i] = nodelist[i].out;	//next[i]初始化指向各顶点边表的第一条边
	
	for (k=0;k<n;k++)								//搜索顶点集合中未被访问的顶点k，并从此出发遍历该顶点的生成子树
	{
		if (nodelist[k].mark==false)				//此顶点未被访问过
		{
			i=k;
			cout<<nodelist[i].letter<<",  ";		//访问此顶点
			nodelist[i].mark=true;					//标记
			notfinish=true;
			
			while (notfinish)
			{
				while( next[i]==0)				//如边表空则可回溯顶点
				{	
					if ( Empty(stack)==1 )		 //若栈空则该顶点的生成子树遍历结束，跳出循环
					{
						notfinish=false;
						cout<<endl;
						break;		
					}
					else Pop(stack, i);			//否则深度搜索路径上的一个顶点出栈
				}			
				if (notfinish)						//检查与第i个顶点相关联的一条尚未搜索的边
				{
					p=next[i]->no;					//指向边的另一端邻接顶点p
					p--;							//因为顶点编号从1开始,而数组下标从0开始
					
					if (nodelist[p].mark==false)				//顺此顶点的深度遍历
					{
						Push(stack,i);							//当前顶点的前驱进栈
						next[i]->mark=true;						//前驱边已访问
						cout<<nodelist[p].letter<<",  ";		//访问此顶点
						nodelist[p].mark=true;					//访问过标记
						next[i] = next[i]->link;				//指向顶点i边表的下一节点(边)
						i=p;									//更换到邻接顶点p的边表			
					}
					else next[i]=next[i]->link;				
				}	//end of if(notfinish)				
			}//end of while(notfinish)		
		}//end of if(nodelist[k].mark==false)	
	}//end of for(k=0;k<n;k++)
}

//图的广度优先遍历（邻接表存储结构）
void WideFSearch(node* nodelist,int n)				
{
	cout<<endl<<"以下进行图的广度优先遍历"<<endl;
	int k,i;
	Queue queue ;
	CreatQueue(queue);
	edge * pE;		
	for (k=0;k<n;k++)						
		nodelist[k].mark=false;					//初始化所有顶点都未被访问过

	for (k=0;k<n;k++)							//搜索顶点集合中未被访问的顶点k，并从此出发遍历该顶点的生成子树(若图示不连通的，最后将形成森林)
	{
		if (nodelist[k].mark==false)			//此顶点未被访问过
		{
			cout<<nodelist[k].letter<<",  ";	//访问此顶点
			nodelist[k].mark=true;				//标记
			
			pE=nodelist[k].out;					//指向顶点i的第一条边
			
			while(pE!=0)
			{				
				if( nodelist[pE->no -1].mark==false)		//该边指向的顶点未被访问过(注意数组nodelist[]从0开始存储)				
					EnQueue(pE->no,queue);					//该顶点邻接的所有未被访问的顶点(边)入队
				pE=pE->link;						
			}
		}//end of if
		while(queue.count!=0)								//队不空
		{	
			DeQueue(i,queue);								//队头出队,顶点（边）编号记录于i
			i--;
			if (nodelist[i].mark==false)
			{
				cout<<nodelist[i].letter<<",  ";			//访问此顶点
				nodelist[i].mark=true;						//标记
				pE=nodelist[i].out;							//指向原队头顶点i的第一条边
				while(pE!=0)
				{				
					if( nodelist[pE->no -1].mark==false)	//该边指向的顶点未被访问过(注意数组nodelist[]从0开始存储)				
						EnQueue(pE->no,queue);				//该顶点邻接的所有未被访问的顶点(边)入队
					pE=pE->link;						
				}
			}			
		}//end of while(queue.count!=0)		
	cout<<endl;
	}//end of for(k=0;k<n;k++)
}