#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 20 //图的最大顶点数
#define MAXQSIZE 30 //队列的最大容量
enum BOOL {False,True};
typedef struct ArcNode
{
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条弧的指针
} ArcNode; //弧结点
typedef struct
{
ArcNode* AdjList[MAX_VERTEX_NUM]; //指向第一条依附该顶点的弧的指针
int vexnum,arcnum; //图的当前顶点和弧数
int GraphKind; //图的种类，0---无向图，1---有向图
} Graph;
typedef struct //队列结构
{
int elem[MAXQSIZE]; //数据域
int front; //队头指针
int rear; //队尾指针
} SqQueue;
BOOL visited[MAX_VERTEX_NUM]; //全局变量——访问标志数组
void CreateGraph ( Graph & ); //生成图的邻接表
void DFSTraverse ( Graph ); //深度优先搜索遍历图
void DFS ( Graph,int );
void BFSTraverse ( Graph ); //广度优先搜索遍历图
void Initial ( SqQueue & ); //初始化一个队列
BOOL QueueEmpty ( SqQueue ); //判断队列是否空
BOOL EnQueue ( SqQueue &,int ); //将一个元素入队列
BOOL DeQueue ( SqQueue &,int & ); //将一个元素出队列
int FirstAdjVex ( Graph,int ); //求图中某一顶点的第一个邻接顶点
int NextAdjVex ( Graph,int,int ); //求某一顶点的下一个邻接顶点
void main()
{
Graph G; //采用邻接表结构的图
char j='y';
textbackground ( 3 ); //设定屏幕颜色
textcolor ( 15 );
clrscr();
//------------------程序解说----------------------------
printf ( "本程序将演示生成一个图，并对它进行遍历.\n" );
printf ( "首先输入要生成的图的种类.\n" );
printf ( "0---无向图, 1--有向图\n" );
printf ( "之后输入图的顶点数和弧数。\n格式：顶点数，弧数；例如:4,3\n" );
printf ( "接着输入各边(弧尾，弧头).\n例如:\n1,2\n1,3\n2,4\n" );
printf ( "程序会生成一个图，并对它进行深度和广度遍历.\n" );
printf ( "深度遍历:1->2->4->3\n广度遍历:1->2->3->4\n" );
//------------------------------------------------------
while ( j!='N'&&j!='n' )
{
printf ( "请输入要生成的图的种类(0/1):" );
scanf ( "%d",&G.GraphKind ); //输入图的种类
printf ( "请输入顶点数和弧数：" );
scanf ( "%d,%d",&G.vexnum,&G.arcnum ); //输入图的顶点数和弧数
CreateGraph ( G ); //生成邻接表结构的图
DFSTraverse ( G ); //深度优先搜索遍历图
BFSTraverse ( G ); //广度优先搜索遍历图
printf ( "图遍历完毕，继续进行吗?(Y/N)" );
scanf ( " %c",&j );
}
}
void CreateGraph ( Graph &G )
{//构造邻接表结构的图G
int i;
int start,end;
ArcNode *s;
for ( i=1; i<=G.vexnum; i++ ) G.AdjList[i]=NULL; //初始化指针数组
for ( i=1; i<=G.arcnum; i++ )
{
scanf ( "%d,%d",&start,&end ); //输入弧的起点和终点
s= ( ArcNode * ) malloc ( sizeof ( ArcNode ) ); //生成一个弧结点
s->nextarc=G.AdjList[start]; //插入到邻接表中
s->adjvex=end;
G.AdjList[start]=s;
if ( G.GraphKind==0 ) //若是无向图，再插入到终点的弧链中
{
s= ( ArcNode * ) malloc ( sizeof ( ArcNode ) );
s->nextarc=G.AdjList[end];
s->adjvex=start;
G.AdjList[end]=s;
}
}
}
void DFSTraverse ( Graph G )
{//深度优先遍历图G
int i;
printf ( "DFSTraverse:" );
for ( i=1; i<=G.vexnum; i++ ) visited[i]=False; //访问标志数组初始化
for ( i=1; i<=G.vexnum; i++ )
if ( !visited[i] ) DFS ( G,i ); //对尚未访问的顶点调用DFS
printf ( "\b\b \n" );
}
void DFS ( Graph G,int i )
{//从第i个顶点出发递归地深度遍历图G
int w;
visited[i]=True; //访问第i个顶点
printf ( "%d->",i );
for ( w=FirstAdjVex ( G,i ); w; w=NextAdjVex ( G,i,w ) )
if ( !visited[w] ) DFS ( G,w ); //对尚未访问的邻接顶点w调用DFS
}
void BFSTraverse ( Graph G )
{//按广度优先非递归的遍历图G，使用辅助队列Q和访问标志数组visited
int i,u,w;
SqQueue Q;
printf ( "BFSTreverse:" );
for ( i=1; i<= G.vexnum; i++ ) visited[i]=False; //访问标志数组初始化
Initial ( Q ); //初始化队列
for ( i=1; i<=G.vexnum; i++ )
if ( !visited[i] )
{
visited[i]=True; //访问顶点i
printf ( "%d->",i );
EnQueue ( Q,i ); //将序号i入队列
while ( !QueueEmpty ( Q ) ) //若队列不空，继续
{
DeQueue ( Q,u ); //将队头元素出队列并置为u
for ( w=FirstAdjVex ( G,u ); w; w=NextAdjVex ( G,u,w ) )
if ( !visited[w] ) //对u的尚未访问的邻接顶点w进行访问并入队列
{
visited[w]=True;
printf ( "%d->",w );
EnQueue ( Q,w );
}
}
}
printf ( "\b\b \n" );
}
int FirstAdjVex ( Graph G,int v )
{//在图G中寻找第v个顶点的第一个邻接顶点
if ( !G.AdjList[v] ) return 0;
else return ( G.AdjList[v]->adjvex );
}
int NextAdjVex ( Graph G,int v,int u )
{//在图G中寻找第v个顶点的相对于u的下一个邻接顶点
ArcNode *p;
p=G.AdjList[v];
while ( p->adjvex!=u ) p=p->nextarc; //在顶点v的弧链中找到顶点u
if ( p->nextarc==NULL ) return 0; //若已是最后一个顶点，返回0
else return ( p->nextarc->adjvex ); //返回下一个邻接顶点的序号
}
void Initial ( SqQueue &Q )
{//队列初始化
Q.front=Q.rear=0;
}
BOOL QueueEmpty ( SqQueue Q )
{//判断队列是否已空，若空返回True,否则返回False
if ( Q.front==Q.rear ) return True;
else return False;
}
BOOL EnQueue ( SqQueue &Q,int ch )
{//入队列，成功返回True，失败返回False
if ( ( Q.rear+1 ) %MAXQSIZE==Q.front ) return False;
Q.elem[Q.rear]=ch;
Q.rear= ( Q.rear+1 ) %MAXQSIZE;
return True;
}
BOOL DeQueue ( SqQueue &Q,int &ch )
{//出队列,成功返回True，并用ch返回该元素值，失败返回False
if ( Q.front==Q.rear ) return False;
ch=Q.elem[Q.front];
Q.front= ( Q.front+1 ) %MAXQSIZE;
return True; //成功出队列，返回True
}