图的遍历.cpp

C++经典算法源码绝对的经典好的算法源码

//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :5  (5_1)                   *
//*PROGRAM          :图的遍历                   *
//*CONTENT          :生成，深度、广度优先遍历   *
//* * * * * * * * * * * * * * * * * * * * * * * *
#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
}