dfs_bfs.cpp

图论中二种遍历图的算法.深度优先遍历,与广度优先遍历.

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>

#define TRUE  1
#define OK    1
#define ERROR -1
#define OVERFLOW -1
#define FALSE 0

#define MAX_VERTEX_NUM   25
#define MAX_NAME  5
#define MAX_INFO  20

int visited[MAX_VERTEX_NUM];
typedef int VRType;   
typedef char InfoType;
typedef char VertexType[MAX_NAME];
typedef VRType QElemType;

int(*VisitFunc)(VertexType);
void vi(QElemType);
typedef struct QNode{

 QElemType data;
 QNode *next;

}*QueuePtr;

typedef struct{

 QueuePtr front,rear;

}LinkQueue;

typedef struct{
 
  VRType adj;    //顶点关系图
  InfoType *info;//该弧相关信息的指针

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct{
 
  VertexType vexs[MAX_VERTEX_NUM]; //顶点向量
  AdjMatrix arcs;      //邻接矩阵
  int vexnum,arcnum;  //图的当前顶点数和弧数
}MGraph; 

//以下定义队列的基本操作函数


int InitQueue(LinkQueue &Q)
{
  //构造一个空队列Q
  if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))))
	  exit(OVERFLOW);
  Q.front->next=NULL;
  return OK;
}

int DestroyQueue(LinkQueue &Q)
{
  //销毁队列Q(无论空否均可)
	while(Q.front){
	Q.rear=Q.front->next;
	free(Q.front);
	Q.front=Q.rear;
	}
	return OK;
}

int QueueEmpty(LinkQueue &Q)
{
  //若Q为空队列,则返回TRUE,否则返回FALSE
  if(Q.front==Q.rear)
	  return TRUE;
  else 
	  return FALSE;
}

int EnQueue(LinkQueue &Q,QElemType e)
{
  //插入元素e为Q的新的队尾元素
  QueuePtr p;
  if(!(p=(QueuePtr)malloc(sizeof(QNode))))
	  exit(OVERFLOW);
  p->data=e;
  p->next=NULL;
  Q.rear->next=p;
  Q.rear=p;
  return OK;
}

int DeQueue(LinkQueue &Q,QElemType e)
{
  //若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR
  QueuePtr p;
  if(Q.front==Q.rear)
	  return ERROR;
  p=Q.front->next;
  e=p->data;
  Q.front->next=p->next;
  if(Q.rear==p)
	  Q.rear=Q.front;
  free(p);
  return OK;
}

int QueueTraverse(LinkQueue Q,void(*vi)(QElemType))
{
  //遍历队列,一旦vi失败,则操作失败
  QueuePtr p;
  p=Q.front->next;
  while(p){
   vi(p->data);
   p=p->next;
  }
  putchar(10);
  return OK;
}
int LocateVex(MGraph &G,VertexType u)
{
  //若G中存在顶点u,则返回该顶点在图中位置,否则返回-1
  int i;
  for(i=0;i<G.vexnum;++i)
    if(strcmp(u,G.vexs[i])==0)
    return i;
  return -1;
}


int CreatDG(MGraph &G)
{
  //采用邻接矩阵表示法,构造有向图G
  int i,j,k,l,IncInfo;
  char s[MAX_INFO],*info;
  VertexType va,vb;
  printf("请输入有向图G的顶点数,弧数,弧是否含有其它信息(是:1,否:0):");
  scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo);
  printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);
  
  for(i=0;i<G.vexnum;i++)
	  scanf("%s",G.vexs[i]);
  for(i=0;i<G.vexnum;i++)
	  for(j=0;j<G.vexnum;j++){
	   G.arcs[i][j].adj=0;
	   G.arcs[i][j].info=NULL;
	  }
  printf("请输入%d条弧的弧尾 弧头(以空格作为间隔): \n",G.arcnum);
  for(k=0;k<G.arcnum;k++){
   scanf("%s%s%*c",va,vb);
   i=LocateVex(G,va);
   j=LocateVex(G,vb);
   G.arcs[i][j].adj=1;    //有向图
   if(IncInfo){
     printf("请输入该弧的相关信息(<%d个字符): ",MAX_INFO);
	 gets(s);
	 l=strlen(s);
	 if(l){
	  info=(char *)malloc(2*sizeof(char));
	  strcpy(info,s);
	  G.arcs[i][j].info=info;
	 }
   }
  
  }
  return OK;
}

VertexType& GetVex(MGraph G,int v)
{
  //返回图中顶点号为v的值 
  char s[]="error";
  if(v>=G.vexnum||v<0)
	  exit(ERROR);
  return G.vexs[v];

}

int FirstAdjVex(MGraph G,VertexType v)
{
  //返回v的第一个邻接顶点的序号.若无邻接顶点,则返回-1
 int i,j=0,k;
 k=LocateVex(G,v);
 for(i=0;i<G.vexnum;i++)
	 if(G.arcs[k][i].adj!=j)
		 return i;
	 return -1;

}

int NextAdjVex(MGraph G,VertexType v,VertexType w)
{
  //返回v的下一个邻接顶点的序号,若w是v的最后一个邻接顶点,则返回-1
  int i,j=0,k1,k2;
  k1=LocateVex(G,v);
  k2=LocateVex(G,w);
  for(i=k2+1;i<G.vexnum;i++)
	  if(G.arcs[k1][i].adj!=j)
		  return i;
	  return -1;
}

void DFS(MGraph G,int v)
{
  //从第v个顶点出发,递归地深度优先遍历图G.
  VertexType w1,v1;
  int w;
  visited[v]=TRUE;
  VisitFunc(G.vexs[v]);
  strcpy(v1,GetVex(G,v));
  for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,GetVex(G,w))))
	  if(!visited[w])
		  DFS(G,w);
}

void DFSTraverse(MGraph G,int(*Visit)(VertexType))
{
  //从第一个顶点开始,深度优先遍历图G.对每个顶点调用函数visit一次且仅一次,
  //一旦visit失败,则操作失败.
  int v;
  VisitFunc=Visit;
  for(v=0;v<G.vexnum;v++)
	  visited[v]=FALSE;
  for(v=0;v<G.vexnum;v++)
	  if(!visited[v])
		  DFS(G,v);
 putchar(10);
}
void BFSTraverse(MGraph G,int(*Visit)(VertexType))
{
  //从第1个顶点起,按广度优先非递归遍历图G.对每个顶点调用函数visit一次且仅一次,
  //一旦visit失败,则操作失败.使用辅助队列Q和访问标志数组visited.
  int v,u=0,w;
  VertexType w1,v1;
  LinkQueue Q;
  for(v=0;v<G.vexnum;v++)
    visited[v]=FALSE;//置初值
  InitQueue(Q);//置空的辅助队列
  for(v=0;v<G.vexnum;v++)
	  if(!visited[v]){ //未被访问
	   visited[v]=TRUE;//置访问标志为TRUE
	   Visit(G.vexs[v]);
	   EnQueue(Q,v);
	   while(!QueueEmpty(Q)){
	   DeQueue(Q,u);
	  strcpy(v1,GetVex(G,v));//****************
      for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,GetVex(G,w))))
	   if(!visited[w])
		  {
		    visited[w]=TRUE;
			Visit(G.vexs[w]);
			EnQueue(Q,w);
	
		  }
	  
	   }
	 }
	putchar(10);
}

int visit(VertexType v)
{
  printf("%s ",v);
  return 1;
}

void vi(QElemType v)
{
  printf("%d ",v);
  return ;
}
void Display(MGraph G)
{
  //输出邻接矩阵
  int i,j;
  char s[7],s1[3];
  strcpy(s,"有向图");
  strcpy(s1,"弧");
  printf("%d个顶点%d条%s的%s\n",G.vexnum,G.arcnum,s1,s);
  for(i=0;i<G.vexnum;i++)
	  printf("G.vexs[%d]=%s\n",i,G.vexs[i]);
  printf("G.arcs.adj:\n");
  for(i=0;i<G.vexnum;i++){
    for(j=0;j<G.vexnum;j++)
		printf("%8d",G.arcs[i][j].adj);
	   putchar(10);
  }
}
void DestroyGraph(MGraph &G)
{
  int i,j;
  for(i=0;i<G.vexnum;i++){
    for(j=0;j<G.vexnum;j++)
		if(G.arcs[i][j].adj==1&&G.arcs[i][j].info){
		 
			free(G.arcs[i][j].info);
			G.arcs[i][j].info=NULL;
		}
   }
  G.vexnum=0;
  G.arcnum=0;
}
void main()
{
  MGraph g; 
  CreatDG(g);
  Display(g);
  printf("深度优先搜索的结果:\n");
  DFSTraverse(g,visit);
  printf("广度优先搜索的结果:\n");
  BFSTraverse(g,visit);
  DestroyGraph(g);
   return ;
}