图的深度优先遍历与广度优先遍历

准备：图的邻接表与队列

#include<stdlib.h>

#include<iostream>
using namespace std;
#define max 20    //顶点数
typedef enum{
DG,DN,UDG,UDN
}graphkind;
typedef int datatype;
typedef char vertextype;
typedef struct node
{
int adjevc;
int weight;
struct node *nextarc;
}arcnode;
typedef struct 
{
vertextype data;
arcnode *firstarc;
}vnode;
typedef struct 
{
vnode vexs[max];
int vexnum,arcnum;
graphkind kind;
}graph;
typedef struct 
{
datatype data[max];
int front,rear;
}queue;
void initqueue(queue *p)
{
p->front=p->rear=0;
}
int emptyqueue(queue *p)
{
return(p->front==p->rear? 1:0);
}
int fullqueue(queue *p)
{
return(p->front==(p->rear+1)%max? 1:0);
}
int inqueue(queue *p,datatype x)
{
if(fullqueue(p))
return 0;
p->rear=(p->rear+1)%max;
p->data[p->rear]=x;
return 1;
}
int outqueue(queue *p,datatype &x)
{
if(emptyqueue(p))
return 0;
p->front=(p->front+1)%max;
x=p->data[p->front];
return 1;

}

深度优先遍历的实现：

int visit[max]={0};        //访问标志 
void out(graph *p,int v)   //访问第v个顶点，并做标记 
{
if(!visit[v])
{
 cout<<p->vexs[v].data;
    }  
visit[v]=1;
}
void DFS(graph *p,int v)
{
arcnode *s;
out(p,v);
s=p->vexs[v].firstarc->nextarc;
while(s!=NULL)
{
 if(!visit[s->adjevc])
 {
  out(p,s->adjevc);
 }
 s=s->nextarc;
} 
}
void DFST(graph *p)
{
if(p==NULL)
{
cout<<"no graph"<<endl;
return ;
}
for(int i=0;i<p->vexnum;i++)
{
DFS(p,i);
}
cout<<endl;

}

广度优先遍历：

void BFS(graph *s)
{
arcnode *t;
queue *p;
int i;
if(s==NULL)
{
cout<<"no graph"<<endl;
return ;
}
p=new queue;
initqueue(p);
inqueue(p,s->vexs[0].firstarc->adjevc);    //第一个顶点入队
out(s,s->vexs[0].firstarc->adjevc);       //访问第一个顶点
while(!emptyqueue(p))    
{
 outqueue(p,i);
 t=s->vexs[i].firstarc;
 while(t!=NULL)
 {
  if(!visit[t->adjevc])
  {
  out(s,t->adjevc);
  inqueue(p,t->adjevc);
}
t=t->nextarc;
 }
}
for(int i=0;i<s->vexnum;i++)
{
if(!visit[i])
{
out(s,i);
}
}
cout<<endl;

}

深度优先遍历如下图：

广度优先遍历如下图：