连通图里的深度优先和广度优先遍历

从图中的某个顶点出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使得每个顶点仅被访问一次，这个过程称为图的遍历。图的遍历有两种：深度优先遍历和广度优先遍历。

　　图分为连通图和非连通图，这里主要讨论连通图的深度、广度优先遍历。

　　一、深度优先遍历

　　图的深度优先遍历类似于树的先序遍历，它的基本思想是：首先访问指定的起始顶点 v v v, 然后选取与 v v v邻接的未被访问的任意一个顶点 w w w, 访问之，再选取与 w w w邻接的未被访问的任一顶点，访问之。

　　重复进行如上的访问，当一个顶点所有邻接顶点都被访问过时，则依次退回到最近被访问过的顶点，若它还有邻接顶点未被访问过，则从这些未被访问的顶点中取出一个顶点开始访问，直到所有的顶点都被访问过为止。

　　以邻接表为存储结构的深度优先遍历算法如下（其中， v v v是初始顶点编号，visited[]是一个全局数组，初始时所有元素均为1）：

int visited[MAXV];
//连通图的深度优先遍历
void DFS(ALGraph *G,int v){ //G指向某个邻接表，v是起始顶点
	ArcNode *p;
	visited[v]=1;                         //已访问，则置1
	printf("%3d",v);					  //输出被访问顶点的编号
	p=G->adjlist[v].firstarc;             //p指向顶点v的第一条弧的弧头结点
	while (p!=NULL)                     
	{
		if(visited[p->adjvex]==0)        //若p->adjvex顶点未访问，递归访问它
			DFS(G,p->adjvex);
		p=p->nextarc;                   //p指向顶点v的下一条弧的弧头结点
	}
	
}

二、广度优先遍历

　　图的广度优先遍历(又叫宽度优先遍历)类似于树的层次遍历，它的基本思想是：首先访问指定的起始顶点 v v v, 然后选取与 v v v邻接的全部顶点$w_1,w_2, \cdots w_t , 再依次访问与 , 再依次访问与 ,再依次访问与w_1,w_2, \cdots w_t $邻接的全部顶点(已被访问的顶点除外)，再从这些被访问的顶点出发，逐次访问与它们邻接的全部顶点（已被访问的顶点除外）。依此类推，直到所有的顶点都被访问过为止。

　　以邻接表为存储结构，用广度优先搜索遍历图时，需要使用一个队列，对应的算法如下：

//连通图的广度优先遍历
void BFS(ALGraph *G,int v){ //G指向某个邻接表,v是起始顶点
	ArcNode *p;
	int queue[MAXV],front=0,rear=0;      //定义循环队列并初始化
	int visited[MAXV];                   //定义存放结点的访问标志的数组
	int w,i;
	for(i=0;i< G->n;i++) visited[i]=0;   //访问标志数组初始化
	printf("%3d",v);                     //输出被访问顶点的编号
	visited[v]=1;                        //置已访问标记
	rear=(rear+1)%MAXV;
	queue[rear]=v;                      //v进队
	while (front!=rear)                 //若队列不空时循环
	{
		front=(front+1)%MAXV;
		w=queue[front];                //出队并赋给w
		p=G->adjlist[w].firstarc;      //找与顶点w邻接的第一个顶点
		while (p!=NULL)
		{
			if (visited[p->adjvex]==0)  //若当前邻接顶点未访问
			{
				printf("%3d",p->adjvex); //访问相邻顶点
				visited[p->adjvex]=1;    //置该顶点已被访问的标志
				rear=(rear+1)%MAXV;      //该顶点进队
				queue[rear]=p->adjvex;
			}
			p=p->nextarc;             //找下一个邻接顶点
		}
	}
	printf("\n");
}

完整代码如下：

//GraphBase.h
typedef int InfoType;
#define MAXV 100       //最大顶点个数

//定义邻接矩阵类型
typedef struct{
	int no;          //顶点编号
	InfoType info;   //顶点其他信息
}VertexType;       //顶点类型

typedef struct{            //图的定义
	int edges[MAXV][MAXV]; //邻接矩阵
	int vexnum,arcnum;     //顶点数，弧数
	VertexType vexs[MAXV]; //存放顶点信息
}MGraph;                   //图的邻接矩阵类型

//定义邻接表类型
typedef struct ANode{         //弧的结点结构类型
	int adjvex;               //该弧的终点位置 
	struct ANode *nextarc;     //指向下一条弧的指针
	InfoType info;             //弧的相关信息,用来存放权值
}ArcNode;
typedef int Vertex;
typedef struct Vnode{      //邻接表头结点的类型
	Vertex data;           //顶点信息
	ArcNode *firstarc;     //指向第一条弧
}VNode;
typedef VNode AdjList[MAXV]; //AdjList是邻接表类型
typedef struct{
	AdjList adjlist;     //邻接表
	int n,e;             //图中顶点数n和边数
}ALGraph;                //图的邻接表类型

//主函数.cpp
#include <stdio.h>
#include <malloc.h>
#include "GraphBase.h"
#define INF 32767      //INF表示无穷大,即∞

//将邻接矩阵g转换邻接表G
void MatToList(MGraph g,ALGraph *&G){
	int i,j,n=g.vexnum;                //n为顶点数
	ArcNode *p;
	G=(ALGraph *)malloc(sizeof(ALGraph));  
	for(i=0;i<n;i++)                       //给邻接表中所有头结点的指针域置初值
		G->adjlist[i].firstarc=NULL;
	for (i=0;i<n;i++)                    //检查邻接矩阵中的每个元素
		for (j=n-1;j>=0;j--)
			if (g.edges[i][j]!=0)        //邻接矩阵的当前元素不为0
			{
				p=(ArcNode *)malloc(sizeof(ArcNode));  //创建一个结点*p
				p->adjvex=j;
				p->info=g.edges[i][j];
				p->nextarc=G->adjlist[i].firstarc;   //将*p链接到链表后面
				G->adjlist[i].firstarc=p;
			}
			G->n=n; G->e=g.arcnum;
}

//将邻接表G转换为邻接矩阵g
void ListToMat(ALGraph *G,MGraph &g){
	int i,j,n=G->n;
	ArcNode *p;
	for(i=0;i<n;i++)          //g.edges[i][j]赋初值0
		for(j=0;j<n;j++)
			g.edges[i][j]=0;
	for (i=0;i<n;i++)
	{
		p=G->adjlist[i].firstarc;
		while(p!=NULL){
			g.edges[i][p->adjvex]=p->info;
			p=p->nextarc;
		}			
	}
	g.vexnum=n; g.arcnum=G->e;
		
}

//输出邻接矩阵g
void DispMat(MGraph g){
	int i,j;
	for (i=0;i<g.vexnum;i++)
	{
		for(j=0;j<g.vexnum;j++)
			if(g.edges[i][j]==INF)
				printf("%3s","∞");
			else
				printf("%3d",g.edges[i][j]);
		printf("\n");
	}

}

//输出邻接表G
void DispAdj(ALGraph *G){
	int i;
	ArcNode *p;
	for (i=0;i< G->n;i++)
	{
		p=G->adjlist[i].firstarc;
		if(p!=NULL) printf("%3d: ",i);
		while (p!=NULL)
		{
			printf("%3d",p->adjvex);
			p=p->nextarc;
		}
		printf("\n");

	}

}



int visited[MAXV];
//连通图的深度优先遍历
void DFS(ALGraph *G,int v){ //G指向某个邻接表，v是起始顶点
	ArcNode *p;
	visited[v]=1;                         //已访问，则置1
	printf("%3d",v);					  //输出被访问顶点的编号
	p=G->adjlist[v].firstarc;             //p指向顶点v的第一条弧的弧头结点
	while (p!=NULL)                     
	{
		if(visited[p->adjvex]==0)        //若p->adjvex顶点未访问，递归访问它
			DFS(G,p->adjvex);
		p=p->nextarc;                   //p指向顶点v的下一条弧的弧头结点
	}
	
}

//连通图的深度优先遍历(非递归)
void DFS1(ALGraph *G,int v){
	ArcNode *p;
	ArcNode *St[MAXV];
	int top=-1,w,i;
	for(i=0;i< G->n;i++)
		visited[i]=0;
	printf("%3d",v);
	visited[v]=1;
	top++;
	St[top]=G->adjlist[v].firstarc;
	while (top > -1)
	{	
		p=St[top]; top--;
		while (p!=NULL)
		{
			w=p->adjvex;
			if (visited[w]==0)
			{
				printf("%3d",w);
				visited[w]=1;
				top++;
				St[top]=G->adjlist[w].firstarc;
				break;
			}
			p=p->nextarc;
		}
		
	}
	printf("\n");
}

//连通图的广度优先遍历
void BFS(ALGraph *G,int v){ //G指向某个邻接表,v是起始顶点
	ArcNode *p;
	int queue[MAXV],front=0,rear=0;      //定义循环队列并初始化
	int visited[MAXV];                   //定义存放结点的访问标志的数组
	int w,i;
	for(i=0;i< G->n;i++) visited[i]=0;   //访问标志数组初始化
	printf("%3d",v);                     //输出被访问顶点的编号
	visited[v]=1;                        //置已访问标记
	rear=(rear+1)%MAXV;
	queue[rear]=v;                      //v进队
	while (front!=rear)                 //若队列不空时循环
	{
		front=(front+1)%MAXV;
		w=queue[front];                //出队并赋给w
		p=G->adjlist[w].firstarc;      //找与顶点w邻接的第一个顶点
		while (p!=NULL)
		{
			if (visited[p->adjvex]==0)  //若当前邻接顶点未访问
			{
				printf("%3d",p->adjvex); //访问相邻顶点
				visited[p->adjvex]=1;    //置该顶点已被访问的标志
				rear=(rear+1)%MAXV;      //该顶点进队
				queue[rear]=p->adjvex;
			}
			p=p->nextarc;             //找下一个邻接顶点
		}
	}
	printf("\n");
}

void main()
{
	int i,j;
	MGraph g;
	ALGraph *G;
	int A[6][6]={
		{0,5,0,5,5,0},
		{0,0,4,0,4,0},
		{0,0,0,0,0,9},
		{0,0,0,0,0,0},
		{0,0,5,7,0,7},
		{0,0,0,0,0,0}
	};

	g.vexnum=6; g.arcnum=10;
	for (i=0;i<g.vexnum;i++)
		for(j=0;j<g.vexnum;j++)
			g.edges[i][j]=A[i][j];
	printf("\n");
	printf(" 有向图G的邻接矩阵: \n");
	DispMat(g);

	G=(ALGraph *)malloc(sizeof(ALGraph));
	printf(" 图G的邻接矩阵转换为邻接表: \n");
	MatToList(g,G);
	DispAdj(G);

// 	printf(" 图G的邻接表转换为邻接矩阵: \n");
// 	ListToMat(G,g1);
// 	DispMat(g1);
// 	printf("\n");

	printf("深度优先遍历：\n");
	DFS(G,0);
	printf("\n");

	printf("深度优先遍历：\n");
	BFS(G,0);
	printf("\n");


}

效果如下：

连通图里的深度优先和广度优先遍历

图(1) 有向图G的深度优先和广度优先遍历；邻接表输出时，由于结点3和结点5的出度都为0，所以是空表即对应的单链表不输出，而结点0、1、2和4的出度都大于0，所以有输出

连通图里的深度优先和广度优先遍历

继续阅读

swmm与lisflood-fp源码如何一起编译 CMake命令

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

Windows下VS开发环境环境安装工程项目设置关于Debug和Release的提示

一文看懂字符串的加减乘除

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

C++实现简单顺序表

笔试面试题目：滑动窗口(二)

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

C经典书籍笔记——C陷阱与缺陷②(语法陷阱之优先级)一、错误案列二、优先级规律

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

线性表之顺序表的实现

C++判断素数、求最大公约数代码判断一个数是否为素数求两个数的最大公约数

SequoiaDB巨杉数据库C++驱动概述

hdu7108哈希