数据结构与算法 ---- 图的广度优先搜索（BFS）和深度优先搜索（DFS）

1.前言

和树的遍历类似，图的遍历也是从图中某点出发，然后按照某种方法对图中所有顶点进行访问，且仅访问一次。

但是图的遍历相对树而言要更为复杂。因为图中的任意顶点都可能与其他顶点相邻，所以在图的遍历中必须记录已被访问的顶点，避免重复访问。

根据搜索路径的不同，我们可以将遍历图的方法分为两种：广度优先搜索和深度优先搜索。

2.图的基本概念

2.1.无向图和无向图
顶点对(u，v)是无序的，即（u，v）和（v，u）是同一条边。常用一对圆括号表示。

顶点对<u,v>是有序的，它是指从顶点u到顶点 v的一条有向边。其中u是有向边的始点，v是有向边的终点。常用一对尖括号表示。

2.2.权和网
图的每条边上可能存在具有某种含义的数值，称该数值为该边上的权。而这种带权的图被称为网。

2.3.连通图与非连通图
连通图：在无向图G中，从顶点v到顶点v’有路径，则称v和v’是联通的。若图中任意两顶点v、v’∈V，v和v’之间均联通，则称G是连通图。上述两图均为连通图。

非连通图：若无向图G中，存在v和v’之间不连通，则称G是非连通图。

3.广度优先搜索

3.1.算法的基本思路
广度优先搜索类似于树的层次遍历过程。它需要借助一个队列来实现。如图2-1-1所示，要想遍历从v0到v6的每一个顶点，我们可以设v0为第一层，v1、v2、v3为第二层，v4、v5为第三层，v6为第四层，再逐个遍历每一层的每个顶点。

具体过程如下：

1.准备工作：创建一个visited数组，用来记录已被访问过的顶点；创建一个队列，用来存放每一层的顶点；初始化图G。

2.从图中的v0开始访问，将的visited[v0]数组的值设置为true，同时将v0入队。

3.只要队列不空，则重复如下操作：

(1)队头顶点u出队。

(2)依次检查u的所有邻接顶点w，若visited[w]的值为false，则访问w，并将visited[w]置为true，同时将w入队。

3.2.算法的实现过程
白色表示未被访问，灰色表示即将访问，黑色表示已访问。

visited数组：0表示未访问，1表示以访问。

队列：队头出元素，队尾进元素。

1.初始时全部顶点均未被访问，visited数组初始化为0，队列中没有元素。

2.即将访问顶点v0。

3.访问顶点v0，并置visited[0]的值为1，同时将v0入队。

4.将v0出队，访问v0的邻接点v2。判断visited[2]，因为visited[2]的值为0，访问v2。

5.将visited[2]置为1，并将v2入队。

6.访问v0邻接点v1。判断visited[1],因为visited[1]的值为0，访问v1。

7.将visited[1]置为0，并将v1入队。

8.判断visited[3],因为它的值为0，访问v3。将visited[3]置为0，并将v3入队。

9.v0的全部邻接点均已被访问完毕。将队头元素v2出队，开始访问v2的所有邻接点。

开始访问v2邻接点v0，判断visited[0]，因为其值为1，不进行访问。

继续访问v2邻接点v4，判断visited[4]，因为其值为0，访问v4，如下图：

10.将visited[4]置为1，并将v4入队。

11.v2的全部邻接点均已被访问完毕。将队头元素v1出队，开始访问v1的所有邻接点。

开始访问v1邻接点v0，因为visited[0]值为1，不进行访问。

继续访问v1邻接点v4，因为visited[4]的值为1，不进行访问。

继续访问v1邻接点v5，因为visited[5]值为0，访问v5，如下图：

12.将visited[5]置为1，并将v5入队。

13.v1的全部邻接点均已被访问完毕，将队头元素v3出队，开始访问v3的所有邻接点。

开始访问v3邻接点v0，因为visited[0]值为1，不进行访问。

继续访问v3邻接点v5，因为visited[5]值为1，不进行访问。

14.v3的全部邻接点均已被访问完毕，将队头元素v4出队，开始访问v4的所有邻接点。

开始访问v4的邻接点v2，因为visited[2]的值为1，不进行访问。

继续访问v4的邻接点v6，因为visited[6]的值为0，访问v6，如下图：

15.将visited[6]值为1，并将v6入队。

16.v4的全部邻接点均已被访问完毕，将队头元素v5出队，开始访问v5的所有邻接点。

开始访问v5邻接点v3，因为visited[3]的值为1，不进行访问。

继续访问v5邻接点v6，因为visited[6]的值为1，不进行访问。

17.v5的全部邻接点均已被访问完毕，将队头元素v6出队，开始访问v6的所有邻接点。

开始访问v6邻接点v4，因为visited[4]的值为1，不进行访问。

继续访问v6邻接点v5，因为visited[5]的值文1，不进行访问。

18.队列为空，退出循环，全部顶点均访问完毕。

4.深度优先搜索

4.1算法的基本思路
深度优先搜索类似于树的先序遍历，具体过程如下：

准备工作：创建一个visited数组，用于记录所有被访问过的顶点。

1.从图中v0出发，访问v0。

2.找出v0的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复此步骤，直至刚访问过的顶点没有未被访问的邻接点为止。

3.返回前一个访问过的仍有未被访问邻接点的顶点，继续访问该顶点的下一个未被访问领接点。

4.重复2,3步骤，直至所有顶点均被访问，搜索结束。

4.2算法的实现过程
1.初始时所有顶点均未被访问，visited数组为空。

2.即将访问v0。

3.访问v0，并将visited[0]的值置为1。

4.访问v0的邻接点v2，判断visited[2]，因其值为0，访问v2。

5.将visited[2]置为1。

6.访问v2的邻接点v0，判断visited[0]，其值为1，不访问。

继续访问v2的邻接点v4，判断visited[4]，其值为0，访问v4。

7.将visited[4]置为1
8.访问v4的邻接点v1，判断visited[1]，其值为0，访问v1。

9.将visited[1]置为1。

10.访问v1的邻接点v0，判断visited[0]，其值为1，不访问。

继续访问v1的邻接点v4，判断visited[4]，其值为1，不访问。

继续访问v1的邻接点v5，判读visited[5]，其值为0，访问v5。

11.将visited[5]置为1。

12.访问v5的邻接点v1，判断visited[1]，其值为1，不访问。

继续访问v5的邻接点v3，判断visited[3]，其值为0，访问v3。

13.将visited[1]置为1。

14.访问v3的邻接点v0，判断visited[0]，其值为1，不访问。

继续访问v3的邻接点v5，判断visited[5]，其值为1，不访问。

v3所有邻接点均已被访问，回溯到其上一个顶点v5，遍历v5所有邻接点。

访问v5的邻接点v6，判断visited[6]，其值为0，访问v6。

15.将visited[6]置为1。

16.访问v6的邻接点v4，判断visited[4]，其值为1，不访问。

访问v6的邻接点v5，判断visited[5]，其值为1，不访问。

v6所有邻接点均已被访问，回溯到其上一个顶点v5，遍历v5剩余邻接点。

17.v5所有邻接点均已被访问，回溯到其上一个顶点v1。

v1所有邻接点均已被访问，回溯到其上一个顶点v4，遍历v4剩余邻接点v6。

v4所有邻接点均已被访问，回溯到其上一个顶点v2。

v2所有邻接点均已被访问，回溯到其上一个顶点v1，遍历v1剩余邻接点v3。

v1所有邻接点均已被访问，搜索结束。

5.具体代码实现

#include <stdio.h>
#include <queue>
using namespace std;

/*一些量的定义*/
queue<char> q;				//定义一个队列，使用库函数queue
#define MVNum 100			//表示最大顶点个数
bool visited[MVNum];	    //定义一个visited数组，记录已被访问的顶点

/*邻接矩阵存储表示*/
typedef struct AMGraph
{
	char vexs[MVNum];//顶点表
	int arcs[MVNum][MVNum];	//邻接矩阵
	int vexnum, arcnum;	//当前的顶点数和边数
}AMGraph;

void visited_init(AMGraph &G)
{
	int v;
	for (v = 0; v < G.vexnum; v++)
		visited[v] = 0;							//将visited数组初始化
}

/*找到顶点v的对应下标*/
int LocateVex(AMGraph &G, char v)
{
	int i;
	for (i = 0; i < G.vexnum; i++)
		if (G.vexs[i] == v)
			return i;
}

/*采用邻接矩阵表示法，创建无向图G*/
int CreateUDG_1(AMGraph &G)
{
	int i, j, k;
	char v1, v2;
	printf("输入总顶点数，总边数:\n");
	scanf("%d %d", &G.vexnum, &G.arcnum);		//输入总顶点数，总边数
	printf("依次输入点的信息:\n");
	for (i = 0; i < G.vexnum; i++){
		getchar();					//获取'\n’，防止其对之后的字符输入造成影响	
		scanf("%c", &G.vexs[i]);			//依次输入点的信息
	}		
	
	for (i = 0; i < G.vexnum; i++)
		for (j = 0; j < G.vexnum; j++)
			G.arcs[i][j] = 0;			//初始化邻接矩阵边，0表示顶点i和j之间无边
	printf("依次输入一条边依附的顶点:\n");
	for (k = 0; k < G.arcnum; k++)
	{
		getchar();
		scanf("%c %c", &v1, &v2);			//输入一条边依附的顶点
		i = LocateVex(G, v1);				//找到顶点i的下标
		j = LocateVex(G, v2);				//找到顶点j的下标
		G.arcs[i][j] = G.arcs[j][i] = 1;		//1表示顶点i和j之间有边，无向图不区分方向
	}
	return 0;
}

/*采用邻接矩阵表示图的广度优先遍历*/
void BFS_AM(AMGraph &G,char v0)
{
/*从v0元素开始访问图*/
 
	int u,i,v,w;
	v = LocateVex(G,v0);	 //找到v0对应的下标
	printf("%c ", v0); 	//打印v0
	visited[v] = 1;			//顶点v0已被访问
	q.push(v0);				//将v0入队
 
	while (!q.empty())
	{
		u = q.front();				//将队头元素u出队，开始访问u的所有邻接点
		v = LocateVex(G, u);			//得到顶点u的对应下标
		q.pop();				//将顶点u出队
		for (i = 0; i < G.vexnum; i++)
		{
			w = G.vexs[i];
			if (G.arcs[v][i] && !visited[i])//顶点u和w间有边，且顶点w未被访问
			{
				printf("%c ", w);	//打印顶点w
				q.push(w);		//将顶点w入队
				visited[i] = 1;		//顶点w已被访问
			}
		}
	}
}

/*采用邻接矩阵表示图的深度优先遍历*/
void DFS_AM(AMGraph &G, char v0)
{
	int w,v;
	v = LocateVex(G,v0);	 //找到v0对应的下标
	printf("%c ", v0); 	//打印v0
	visited[v] = 1;			//顶点v0已被访问
	for (w = 0; w < G.vexnum; w++)
		if (G.arcs[v][w]&&!visited[w]) //递归调用
			DFS_AM(G,G.vexs[w]);
}

int main ()
{
	int i;
	char c;
	AMGraph G;
	//BFS_AM(G, 'a');
	CreateUDG_1(G);
	visited_init(G);
	printf("输入开始访问的元素：\n");
	getchar();
	scanf("%c", &c);
	
	//深度优先遍历 
	DFS_AM(G, c);
	
	//广度优先遍历 
	//BFS_AM(G, c);

   	return(0);
}