【数据结构周周练】024 图的经典遍历算法之深度优先搜索、广度优先搜素

一、图的遍历算法简述

上两篇博客给大家讲了图的存储结构：邻接表，邻接矩阵，十字链表以及邻接多重表以及邻接表转化为邻接矩阵的方法。在周周练里，我们只讲了图的算法原理，并没有具体的实现过程，因为我们周周练是一个循序渐进的过程，我们先给大家分享一些基础的内容，然后再逐步深化。

今天要给大家分享的是图的两种遍历算法，深度优先搜索和广度优先搜索，当然以理论为主，同时给大家讲解算法原理以及算法内容，并没有算法具体的测试与应用，后续慢慢会给大家分享，让我们一起从基础开始，从理论开始。

我们知道，图的每一种存储结构其实都可以当作图的遍历，但是这种方式很多结点都会重复遍历，所以，我们希望能找到一种算法，避免重复查找，这就是我们今天要讲的两种遍历算法。

当然为了方便起见，我们将邻接矩阵的每个边初始化为0，在转化过程中，直接寻找存在的边，赋值为1即可。

二、深度优先遍历（DFS）

图的深度优先遍历类似于树的先序遍历，我们借助栈的先进后出的功能，对其进行遍历。

1.基本思想

1.首先访问图的其中一个结点，并置该结点访问标记，然后将该结点存入栈中；

2.然后访问与该结点邻接且未访问的结点，如果存在某邻接结点未被访问，进行与第一个结点相同的操作，如果邻接结点全部访问过，获取栈中栈顶元素进行步骤2。直到进行出栈操作时栈为空，遍历完成。

2.代码

#define MAXVERTEXNUM 100  //Maximum value of the vertex number
bool visited[MAXVERTEXNUM]; // An array of tag for saving visited or not

typedef char VertexType; //the type of vertex

// the graph are storaged by adjacency matrix 邻接矩阵存储图
typedef struct {
	VertexType Vex[MAXVERTEXNUM];
	EdgeType Edge[MAXVERTEXNUM][MAXVERTEXNUM];  // adjacency matrix
	int vexNum, arcNum;  //current vertex number and arc of graph
}MGraph;

//ergodic the graph by Depth-First-Search 深度优先搜索遍历图
void DFSTraverse(MGraph G) {
	for (int i = 0; i < G.vexNum; i++)
		visited[i] = false;
	for (int i = 0; i < G.vexNum; i++)
	{
		if (!visited[i]) {
			DFS(G, i);
		}
	}
}

void DFS(MGraph G,int v){
	visit(v);
	visited[v] = true;
	for (int i = FirstNeighbor(G,v); i >= 0; i = NextNeighbor(G, v, i))
	{
		if (!visited[i]) {
			DFS(G, v);
		}
	}
}

三、广度优先遍历（BFS）

图的广度优先遍历类似于树的层次遍历，我们借助队列的先进先出的功能，对其进行遍历。

1.基本思想

1.首先访问图的其中一个结点，并置该结点访问标记，然后将该结点存入队列中；

2.然后进行出队操作，获取出队元素，并判断该元素所有的邻接点是否已经被访问，若未被访问将其入队；

3.重复进行操作2，直到出队时队列为空，说明遍历完成.

2.代码

#define MAXVERTEXNUM 100  //Maximum value of the vertex number
bool visited[MAXVERTEXNUM]; // An array of tag for saving visited or not

typedef char VertexType; //the type of vertex

// the graph are storaged by adjacency matrix 邻接矩阵存储图
typedef struct {
	VertexType Vex[MAXVERTEXNUM];
	EdgeType Edge[MAXVERTEXNUM][MAXVERTEXNUM];  // adjacency matrix
	int vexNum, arcNum;  //current vertex number and arc of graph
}MGraph;

int visit(int v) {

}

//ergodic the graph by Breadth-First-Search 深度优先搜索遍历图
void BFSTraverse(MGraph G) {
	//Initialization the array
	for (int i = 0; i < G.vexNum; i++) 
	{
		visited[i] = false;
	}
	//Initalization an auxiliary queue
	InitQueue(Q);
	for (int i = 0; i < G.vexNum; i++)
	{
		if (!visited[i]) {
			BFS(G, i);
		}
	}
}

void BFS(MGraph G, int v) {
	visit(v);
	visited[v] = true;
	EnQueue(Q, v);
	while (Q)
	{
		DeQueue(Q, v);
		for (int i = FirstNeighbor(G, v); i >= 0; i = NextNeighbor(G, v, i))
		{
			if (!visited[i]) {
				BFS(G, v);
				visited[v] = true;
				EnQueue(Q, v);
			}
		}
	}
}