在图的结构中常用的遍历方式有两种：深度优先搜索（DFS，也可以叫做深度优先搜索）和广度优先搜索（BFS，也可以叫做深度优先搜索）。
深度优先搜索
深度优先的递归定义
所谓深度优先搜索，是从图中的一个顶点出发，每次遍历当前访问顶点的临界点，一直到访问的顶点没有未被访问过的临界点为止。然后采用依次回退的方式，查看来的路上每一个顶点是否有其它未被访问的临界点。访问完成后，判断图中的顶点是否已经全部遍历完成，如果没有，以未访问的顶点为起始点，重复上述过程。
图 1 无向图.png
深度优先搜索的过程类似于树的先序遍历，我们从例子中体会深度优先搜索。例如图 1 是一个无向图，采用深度优先算法遍历这个图的过程为：
- 首先任意找一个未被遍历过的顶点，例如从 V1 开始，由于 V1 率先访问过了，所以，需要标记 V1 的状态为访问过；
- 然后遍历 V1 的邻接点，例如访问 V2 ，并做标记，然后访问 V2 的邻接点，例如 V4 （做标记），然后 V8 ，然后 V5 ；
- 当继续遍历 V5 的邻接点时，根据之前做的标记显示，所有邻接点都被访问过了。此时，从 V5 回退到 V8 ，看 V8 是否有未被访问过的邻接点，如果没有，继续回退到 V4 ， V2 ， V1 ；
- 通过查看 V1 ，找到一个未被访问过的顶点 V3 ，继续遍历，然后访问 V3 邻接点 V6 ，然后 V7 ；
- 由于 V7 没有未被访问的邻接点，所有回退到 V6 ，继续回退至 V3 ，最后到达 V1 ，发现没有未被访问的；
- 最后一步需要判断是否所有顶点都被访问，如果还有没被访问的，以未被访问的顶点为第一个顶点，继续依照上边的方式进行遍历。
根据上边的过程，可以得到图 1 通过深度优先搜索获得的顶点的遍历次序为：
V1 -> V2 -> V4 -> V8 -> V5 -> V3 -> V6 -> V7
注意：深度优先搜索是一个不断回溯的过程。
深度优先的实现
关于深度优先实现可以分为两种形式：递归和非递归。这与树中的先序遍历基本没什么差别。
伪代码
1、递归实现
1、访问顶点v: visited[v]=1； //算法执行前visited[n] = 0;
2、w = 顶点v的第一个邻接点；
3、while（w存在）{
if（w未被访问）
从顶点w出发递归执行该算法；
w = 顶点v的下一个邻接点；
}
2、非递归实现
1、 栈S的初始化: visited[n=0]
2、访问顶点v: visited[v]=1; 顶点v入栈s
3、while(栈S非空){
x=栈S的顶元素(不出栈)；
if(存在并找到未曾访问的x邻接点w){
访问w; visited[w]=1;
w入栈；
}else{
x出栈；
}
}
递归方式实现：
#include <stdio.h>
typedef enum{
false,true
}bool; //定义bool型常量
bool visited[20]; //设置全局数组，记录标记顶点是否被访问过
typedef struct {
int adj; //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
char * info; //弧或边额外含有的信息指针
}ArcCell,AdjMatrix[20][20];
typedef struct {
int vexs[20]; //存储图中顶点数据
AdjMatrix arcs; //二维数组，记录顶点之间的关系
int vexnum,arcnum; //记录图的顶点数和弧（边）数
}MGraph;
//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph * G,int v){
int i=0;
//遍历一维数组，找到变量v
for (; i<G->vexnum; i++) {
if (G->vexs[i]==v) {
break;
}
}
//如果找不到，输出提示语句，返回-1
if (i>G->vexnum) {
printf("no such vertex.\n");
return -1;
}
return i;
}
//构造无向图
void CreateDN(MGraph *G){
scanf("%d,%d",&(G->vexnum),&(G->arcnum));
int i,j;
for (i=0; i<G->vexnum; i++) {
scanf("%d",&(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;
}
}
for (i=0; i<G->arcnum; i++) {
int v1,v2;
scanf("%d,%d",&v1,&v2);
int n=LocateVex(G, v1);
int m=LocateVex(G, v2);
if (m==-1 ||n==-1) {
printf("no this vertex\n");
return;
}
G->arcs[n][m].adj=1;
G->arcs[m][n].adj=1;//无向图的二阶矩阵沿主对角线对称
}
}
int FirstAdjVex(MGraph G,int v)
{
int i;
//查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标
for(i = 0; i<G.vexnum; i++){
if( G.arcs[v][i].adj ){
return i;
}
}
return -1;
}
int NextAdjVex(MGraph G,int v,int w)
{
int i;
//从前一个访问位置w的下一个位置开始，查找之间有边的顶点
for(i = w+1; i<G.vexnum; i++){
if(G.arcs[v][i].adj){
return i;
}
}
return -1;
}
void visitVex(MGraph G, int v){
printf("%d ",G.vexs[v]);
}
void DFS(MGraph G,int v){
visited[v] = true;//标记为true
visitVex( G, v); //访问第v 个顶点
//从该顶点的第一个边开始，一直到最后一个边，对处于边另一端的顶点调用DFS函数
int w;
for(w = FirstAdjVex(G,v); w>=0; w = NextAdjVex(G,v,w)){
//如果该顶点的标记位false，证明未被访问，调用深度优先搜索函数
if(!visited[w]){
DFS(G,w);
}
}
}
//深度优先搜索
void DFSTraverse(MGraph G){//
int v;
//将用做标记的visit数组初始化为false
for( v = 0; v < G.vexnum; ++v){
visited[v] = false;
}
//对于每个标记为false的顶点调用深度优先搜索函数
for( v = 0; v < G.vexnum; v++){
//如果该顶点的标记位为false，则调用深度优先搜索函数
if(!visited[v]){
DFS( G, v);
}
}
}
int main() {
MGraph G;//建立一个图的变量
CreateDN(&G);//初始化图
DFSTraverse(G);//深度优先搜索图
return 0;
}
执行结果.png
广度优先搜索
广度优先搜索类似于树的层次遍历。从图中的某一顶点出发，遍历每一个顶点时，依次遍历其所有的邻接点，然后再从这些邻接点出发，同样依次访问它们的邻接点。按照此过程，直到图中所有被访问过的顶点的邻接点都被访问到。
最后还需要做的操作就是查看图中是否存在尚未被访问的顶点，若有，则以该顶点为起始点，重复上述遍历的过程。
还拿图 1 中的无向图为例，假设 V1 作为起始点，遍历其所有的邻接点 V2 和 V3 ，以 V2 为起始点，访问邻接点 V4 和 V5 ，以 V3 为起始点，访问邻接点 V6 、 V7 ，以 V4 为起始点访问 V8 ，以 V5 为起始点，由于 V5 所有的起始点已经全部被访问，所有直接略过， V6 和 V7 也是如此。
以 V1 为起始点的遍历过程结束后，判断图中是否还有未被访问的点，由于图 1 中没有了，所以整个图遍历结束。遍历顶点的顺序为：
V1 -> V2 -> v3 -> V4 -> V5 -> V6 -> V7 -> V8
伪代码实现：
1、初始化对列Q;visited[n]=0
2、访问顶点v；visited[v]=1;顶点v入队列Q；
3、while(队列Q非空){
v = 队列的队首元素出队；
w = 顶点v的第一个邻接点；
while(w存在){
如果w为访问，则访问顶点w；
visited[w]=1;
顶点w入队列Q;
w=顶点v的下一个邻接点.
}
}
广度优先搜索借助辅助队列实现代码：
#include <stdio.h>
typedef enum{false,true}bool; //定义bool型常量
bool visited[20]; //设置全局数组，记录标记顶点是否被访问过
typedef struct Queue{
int data;
struct Queue * next;
}Queue;
typedef struct {
int adj; //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
char * info; //弧或边额外含有的信息指针
}ArcCell,AdjMatrix[20][20];
typedef struct {
int vexs[20]; //存储图中顶点数据
AdjMatrix arcs; //二维数组，记录顶点之间的关系
int vexnum,arcnum; //记录图的顶点数和弧（边）数
}MGraph;
//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph * G,int v){
int i=0;
//遍历一维数组，找到变量v
for (; i<G->vexnum; i++) {
if (G->vexs[i]==v) {
break;
}
}
//如果找不到，输出提示语句，返回-1
if (i>G->vexnum) {
printf("no such vertex.\n");
return -1;
}
return i;
}
//构造无向图
void CreateDN(MGraph *G){
scanf("%d,%d",&(G->vexnum),&(G->arcnum));
int i ,j;
for (i=0; i<G->vexnum; i++) {
scanf("%d",&(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;
}
}
for (i=0; i<G->arcnum; i++) {
int v1,v2;
scanf("%d,%d",&v1,&v2);
int n=LocateVex(G, v1);
int m=LocateVex(G, v2);
if (m==-1 ||n==-1) {
printf("no this vertex\n");
return;
}
G->arcs[n][m].adj=1;
G->arcs[m][n].adj=1;//无向图的二阶矩阵沿主对角线对称
}
}
int FirstAdjVex(MGraph G,int v)
{
int i;
//查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标
for(i = 0; i<G.vexnum; i++){
if( G.arcs[v][i].adj ){
return i;
}
}
return -1;
}
int NextAdjVex(MGraph G,int v,int w)
{
int i;
//从前一个访问位置w的下一个位置开始，查找之间有边的顶点
for(i = w+1; i<G.vexnum; i++){
if(G.arcs[v][i].adj){
return i;
}
}
return -1;
}
//初始化队列
void InitQueue(Queue ** Q){
(*Q)=(Queue*)malloc(sizeof(Queue));
(*Q)->next=NULL;
}
//顶点元素v进队列
void EnQueue(Queue **Q,int v){
Queue * element=(Queue*)malloc(sizeof(Queue));
element->data=v;
(*Q)->next = element;
element->next = NULL;
*Q = element;
}
//队头元素出队列
void DeQueue(Queue **Q,int *u){
(*u)=(*Q)->next->data;
(*Q)->next=(*Q)->next->next;
}
//判断队列是否为空
bool QueueEmpty(Queue *Q){
if (Q->next==NULL) {
return true;
}
return false;
}
//广度优先搜索
void BFSTraverse(MGraph G){//
int v;
//将用做标记的visit数组初始化为false
for( v = 0; v < G.vexnum; ++v){
visited[v] = false;
}
//对于每个标记为false的顶点调用深度优先搜索函数
Queue * Q;
InitQueue(&Q);
for( v = 0; v < G.vexnum; v++){
if(!visited[v]){
visited[v]=true;
printf("%d ",G.vexs[v]);
EnQueue(&Q, G.vexs[v]);
while (!QueueEmpty(Q)) {
int u;
DeQueue(&Q, &u);
u=LocateVex(&G, u);
int w;
for (w=FirstAdjVex(G, u); w>=0; w=NextAdjVex(G, u, w)){
if (!visited[w]) {
visited[w]=true;
printf("%d ",G.vexs[w]);
EnQueue(&Q, G.vexs[w]);
}
}
}
}
}
}
int main() {
MGraph G;//建立一个图的变量
CreateDN(&G);//初始化图
printf("广度优先遍历:");
BFSTraverse(G);//广度优先搜索图
return 0;
}
执行结果.png
9.3 附录（额外的版本）
我们换一种更为容易理解的方式看图的遍历，邻接矩阵深度和广度遍历的实现，利用循环队列，更节省资源消耗，更避免了反复的内存申请与释放。
邻接矩阵深度和广度遍历代码如下：
#include <stdio.h>
typedef struct
{
int vexs[8]; //存储顶点
int arc[8][8]; //存储边的关系
int numVertexes; //顶点个数
int numEdges; //边的个数
}MGraph;
//循环队列的顺序存储结构
typedef struct
{
int data[8];
int front; //头指针
int rear; //尾指针，若队列不空，指向队列尾元素的下一个位置
}Queue;
//初始化一个空队列Q
int InitQueue(Queue *Q)
{
Q->front=0;
Q->rear=0;
return 1;
}
//若队列Q为空队列,则返回1,否则返回0/
int QueueEmpty(Queue Q)
{
if(Q.front==Q.rear){ //队列空的标志
return 1;
}
else{
return 0;
}
}
//若队列未满，则插入元素e为Q新的队尾元素
int EnQueue(Queue *Q,int e)
{
if ((Q->rear+1)%8 == Q->front) //队列满的判断
return 0;
Q->data[Q->rear] = e; //将元素e赋值给队尾
Q->rear=(Q->rear+1)%8; // rear指针向后移一位置，若到最后则转到数组头部
return 1;
}
//若队列不空，则删除Q中队头元素，用e返回其值
int DeQueue(Queue *Q,int *e)
{
if (Q->front == Q->rear){ //队列空的判断
return 0;
}
*e=Q->data[Q->front]; //将队头元素赋值给e
Q->front=(Q->front+1)%9; //front指针向后移一位置，若到最后则转到数组头部
return 1;
}
//创建无向图，8个顶点9个边，固定数据进行初始化，打印矩阵结构
void CreateMGraph(MGraph *G){
int i, j;
G->numEdges=9;
G->numVertexes=8;
//建立顶点表信息
G->vexs[0]= 1;
G->vexs[1]= 2;
G->vexs[2]= 3;
G->vexs[3]= 4;
G->vexs[4]= 5;
G->vexs[5]= 6;
G->vexs[6]= 7;
G->vexs[7]= 8;
//初始化图
for (i = 0; i < G->numVertexes; i++){
for ( j = 0; j < G->numVertexes; j++){
G->arc[i][j]=0;
}
}
G->arc[0][1]=1;
G->arc[1][3]=1;
G->arc[1][4]=1;
G->arc[3][7]=1;
G->arc[4][7]=1;
G->arc[0][2]=1;
G->arc[2][5]=1;
G->arc[2][6]=1;
G->arc[5][6]=1;
for(i = 0; i < G->numVertexes; i++){
for(j = i; j < G->numVertexes; j++){
G->arc[j][i] = G->arc[i][j];
}
}
//生成矩阵形式图结构
for(i = 0; i < G->numVertexes; i++){
for(j = 0; j < G->numVertexes; j++){
printf("%d ", G->arc[i][j]);
}
printf("\n");
}
}
int visited[9]; // 访问标记的数组
//邻接矩阵的深度优先递归算法
void DFS(MGraph G, int i){
int j;
visited[i] = 1;
printf("%d ", G.vexs[i]);// 打印顶点，也可以其它操作
for(j = 0; j < G.numVertexes; j++){
if(G.arc[i][j] == 1 && !visited[j]){
DFS(G, j);// 对为访问的邻接顶点递归调用
}
}
}
//邻接矩阵的深度遍历操作
void DFSTraverse(MGraph G){
int i;
for(i = 0; i < G.numVertexes; i++){
visited[i] = 0; //初始所有顶点状态都是未访问过状态
}
for(i = 0; i < G.numVertexes; i++){
if(!visited[i]){ //对未访问过的顶点调用DFS，若是连通图，只会执行一次
DFS(G, i);
}
}
}
/* 邻接矩阵的广度遍历算法 */
void BFSTraverse(MGraph G){
int i, j;
Queue Q;
for(i = 0; i < G.numVertexes; i++){
visited[i] = 0;
}
InitQueue(&Q); //初始化一辅助用的队列
for(i = 0; i < G.numVertexes; i++){ // 对每一个顶点做循环
if (!visited[i]){ //若是未访问过就处理
visited[i]=1; //设置当前顶点访问过
printf("%d ", G.vexs[i]); //打印顶点，也可以其它操作
EnQueue(&Q,i); //将此顶点入队列
while(!QueueEmpty(Q)) //若当前队列不为空
{
DeQueue(&Q,&i); //将队对元素出队列，赋值给i
for(j=0;j<G.numVertexes;j++){
//判断其它顶点若与当前顶点存在边且未访问过
if(G.arc[i][j] == 1 && !visited[j]){
visited[j]=1; //将找到的此顶点标记为已访问
printf("%d ", G.vexs[j]); //打印顶点
EnQueue(&Q,j); //将找到的此顶点入队列
}
}
}
}
}
}
int main(void)
{
MGraph G;
CreateMGraph(&G);
printf("\n深度遍历：");
DFSTraverse(G);
printf("\n广度遍历：");
BFSTraverse(G);
return 0;
}
image.png
利用邻接矩阵的数据初始化邻接表实现深度和广度遍历
邻接表深度和广度遍历代码如下：
#include <stdio.h>
/* ****************************************************** */
//邻接矩阵结构
typedef struct{
char vexs[8]; // 存储顶点
int arc[8][8]; // 邻接矩阵,可看作边表
int numVertexes; // 顶点数
int numEdges; // 边数
}MGraph;
/* ****************************************************** */
/* ****************************************************** */
//邻接表结构
typedef struct EdgeNode{ //边表结点
int adjvex; //邻接点数据域,存储该顶点对应的下标
int weight; //用于存储权值,对于非网图可以不需要
struct EdgeNode *next; //链域,指向下一个邻接点
}EdgeNode;
typedef struct VertexNode { //顶点表结点
int in; //顶点入度
char data; //顶点域,存储顶点信息
EdgeNode *firstedge; //边表头指针
}VertexNode, AdjList[8];
typedef struct{
AdjList adjList;
int numVertexes,numEdges; //图中当前顶点数和边数
}graphAdjList,*GraphAdjList;
/* ****************************************************** */
/* ****************************************************** */
//用到的队列结构与函数
//循环队列的顺序存储结构
typedef struct{
int data[8];
int front; //头指针
int rear; //尾指针,若队列不空,指向队列尾元素的下一个位置
}Queue;
//初始化一个空队列Q
int InitQueue(Queue *Q){
Q->front=0;
Q->rear=0;
return 1;
}
//若队列Q为空队列,则返回1,否则返回0
int QueueEmpty(Queue Q){
if(Q.front==Q.rear){ //队列空的标志
return 1;
}
else{
return 0;
}
}
//若队列未满,则插入元素e为Q新的队尾元素
int EnQueue(Queue *Q,int e){
if ((Q->rear+1)%8 == Q->front) //队列满的判断
return 0;
Q->data[Q->rear]=e; // 将元素e赋值给队尾
Q->rear=(Q->rear+1)%8; // rear指针向后移一位置, 若到最后则转到数组头部
return 1;
}
//若队列不空,则删除Q中队头元素,用e返回其值
int DeQueue(Queue *Q,int *e){
if (Q->front == Q->rear){ //队列空的判断
return 0;
}
*e=Q->data[Q->front]; //将队头元素赋值给e
Q->front=(Q->front+1)%8; //front指针向后移一位置, 若到最后则转到数组头部
return 1;
}
/* ****************************************************** */
void CreateMGraph(MGraph *G){
int i, j;
G->numEdges=9;
G->numVertexes=8;
//建立顶点表信息
G->vexs[0]= 1;
G->vexs[1]= 2;
G->vexs[2]= 3;
G->vexs[3]= 4;
G->vexs[4]= 5;
G->vexs[5]= 6;
G->vexs[6]= 7;
G->vexs[7]= 8;
//初始化图
for (i = 0; i < G->numVertexes; i++){
for ( j = 0; j < G->numVertexes; j++){
G->arc[i][j]=0;
}
}
G->arc[0][1]=1;
G->arc[1][3]=1;
G->arc[1][4]=1;
G->arc[3][7]=1;
G->arc[4][7]=1;
G->arc[0][2]=1;
G->arc[2][5]=1;
G->arc[2][6]=1;
G->arc[5][6]=1;
for(i = 0; i < G->numVertexes; i++){
for(j = i; j < G->numVertexes; j++){
G->arc[j][i] =G->arc[i][j];
}
}
//生成矩阵形式图结构输出
for(i = 0; i < G->numVertexes; i++){
for(j = 0; j < G->numVertexes; j++){
printf("%d ", G->arc[i][j]);
}
printf("\n");
}
}
//利用邻接矩阵构建邻接表
void CreateALGraph(MGraph G,GraphAdjList *GL){
int i,j;
EdgeNode *e;
*GL = (GraphAdjList)malloc(sizeof(graphAdjList));
(*GL)->numVertexes=G.numVertexes;
(*GL)->numEdges=G.numEdges;
for(i= 0;i <G.numVertexes;i++){ //读入顶点信息,建立顶点表
(*GL)->adjList[i].in=0;
(*GL)->adjList[i].data=G.vexs[i];
(*GL)->adjList[i].firstedge=NULL; // 将边表置为空表
}
for(i=0;i<G.numVertexes;i++){ //建立边表
for(j=0;j<G.numVertexes;j++){
if (G.arc[i][j]==1)
{
e=(EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex=j; //邻接序号为j
e->next=(*GL)->adjList[i].firstedge; //将当前顶点上的指向的结点指针赋值给e
(*GL)->adjList[i].firstedge=e; // 将当前顶点的指针指向e
(*GL)->adjList[j].in++;
}
}
}
}
int visited[8]; // 访问标志的数组
//邻接表的深度优先递归算法
void DFS(GraphAdjList GL, int i){
EdgeNode *p;
visited[i] = 1;
printf("%d ",GL->adjList[i].data);//打印顶点,也可以其它操作
p = GL->adjList[i].firstedge;
while(p){
if(!visited[p->adjvex]){
DFS(GL, p->adjvex);//对为访问的邻接顶点递归调用
}
p = p->next;
}
}
//邻接表的深度遍历操作
void DFSTraverse(GraphAdjList GL)
{
int i;
for(i = 0; i < GL->numVertexes; i++){
visited[i] = 0; // 初始所有顶点状态都是未访问过状态
}
for(i = 0; i < GL->numVertexes; i++){
if(!visited[i]){ //对未访问过的顶点调用DFS,若是连通图,只会执行一次
DFS(GL, i);
}
}
}
//邻接表的广度遍历算法
void BFSTraverse(GraphAdjList GL)
{
int i;
EdgeNode *p;
Queue Q;
for(i = 0; i < GL->numVertexes; i++){
visited[i] = 0;
}
InitQueue(&Q);
for(i = 0; i < GL->numVertexes; i++){
if (!visited[i]){
visited[i]=1;
printf("%d ",GL->adjList[i].data);//打印顶点
EnQueue(&Q,i);
while(!QueueEmpty(Q)){
DeQueue(&Q,&i);
p = GL->adjList[i].firstedge; //找到当前顶点的边表链表头指针
while(p){
if(!visited[p->adjvex]){ //若此顶点未被访问
visited[p->adjvex]=1;
printf("%d ",GL->adjList[p->adjvex].data);
EnQueue(&Q,p->adjvex); //将此顶点入队列
}
p = p->next; //指针指向下一个邻接点
}
}
}
}
}
int main(void){
MGraph G;
GraphAdjList GL;
CreateMGraph(&G);
CreateALGraph(G,&GL);
printf("\n深度遍历:");
DFSTraverse(GL);
printf("\n广度遍历:");
BFSTraverse(GL);
return 0;
}
image.png
