【数据结构基础整理】图--04：深度优先搜索和广度优先

代码实现图的深度优先搜索和广度优先搜索

0x01.深度优先搜索（DFS）

搜索方法说明：

从名字中 可以得知，这个方法根本在于深度，那么何为深度？在树中，我们了解了哟个概念叫树的高度，其实深度就类似于树的高度，那么既然是深度优先，那么我们遍历何查找的时候每一步都应该找到最深处，在树中可以说是遍历到叶结点，然后一个深度遍历完成后，退回来，继续遍历下一个深度。在图中，这个深度应该是指一个顶点的周围顶点都遍历完成了，也需要退回来继续探索下一个深度，可以这么说，图的深度优先遍历，就相当于树的前序遍历。

结论：深度优先搜索其实就是一个不断递进何回溯的过程。

 具体如何实现：

设立标志变量：想要知道一个顶点是否被遍历到，肯定需要一个具体的标志变量，我们可以把这个标志变量单独拿出来作为一个数组，下标与顶点的下标相同。

递归：树的前序遍历适用的是递归，那么图的深度优先搜索也用的是递归，递归能够更简便的完成这个回溯的过程。

代码实现：（对于邻接矩阵创建的图而言）

//深度优先遍历的递归算法
void DFS(Graph*G,int i)
{
	int j;
	printf("%c ", G->ver[i]);
	visited[i] = true;//更新节点访问状态
	for (j = 0; j < G->numv; j++)
	{
		if (G->edge[i][j] != INTMAX && !visited[j])//对该节点的邻接点进行递归调用
		{
			DFS(j);
		}
	}
}

//遍历过程
void DFST(Graph*G)
{
	int i;
	for (i = 0; i < G->numv; i++)//初始化每个节点的访问状态
	{
		visited[i] = false;//这是全局的数组
	}
	for (i = 0; i < G->numv; i++)
	{
		if (!visited[i])//若未访问过
		{
			DFS(&G,i);
		}
	}

}

代码实现：（对于邻接表创建的图而言）

//邻接表的深度优先遍历
void DFS(GraphAdjList GL, int i)
{
	visited[i] = true;
	printf("%c ", GL->adjList[i].data);
	EdgeNode* p = GL->adjList[i].firstedge;
	while (p)
	{
		if (!visited[p->adjvex])
		{
			DFS(GL, p->adjvex);
		}
		p = p->next;
	}
}

void DFST(GraphAdjList GL)
{
	int i;
	for (i = 0; i < GL->numv; i++)
	{
		visited[i] == false;
	}
	for (i = 0; i < G->numv; i++)
	{
		if (!visited[i])
		{
			DFS(GL, i);
		}
	}
}

0x02.广度优先搜索（BFS）

搜索方法说明：

广度是广度优先搜索的关键，那么如何理解广度呢？从字面意思，广度就是宽的，从树的理解来看，这个广度就像是树的同一层上的结点的数目，叫做广度，在树中，按照这种广度来遍历的操作是层序遍历，先把每一层的遍历完再去到下一层，而不是探究每个结点的深度，其实图的广度优先搜索就可以理解成树的层序遍历。

图的广度优先搜索就是先遍历每个顶点的邻接点再去遍历邻接点的邻接点。

具体如何实现： 

在树的层序遍历中，采用了队列这一数据结构，利用了队列的先进先出的特点，把之前遍历的元素先入队，同样，图的深度优先遍历也是一个这样的过程。

队列的相关操作代码实现：

typedef struct {
	int data[MAXSIZE];
	int head;
	int tail;
}Queue;

void IniQueue(Queue* Q)
{
	Q->head = Q->tail = 0;
}

int QueueEmpty(Queue Q)
{
	if (Q.head == Q.tail)
	{
		return 1;
	}
	return 0;
}

void EnQueue(Queue* Q, int m)
{
	//省略判满
	Q->data[Q->tail++] = m;
}

void DeQueue(Queue* Q, int* i)//将队头中元素赋值给i
{
	//省略判空
	*i = Q->data[Q->head++];
}

广度优先搜索代码实现：（基于邻接矩阵）

//广度优先遍历
void BFST(Graph *G)
{
	int i, j;
	Queue Q;
	for (i = 0; i < G->numv; i++)//初始化每个节点的访问状态
	{
		visited[i] = false;
	}
	IniQueue(&Q);
	for (i = 0; i < G->numv; i++)
	{
		if (!visited[i])//若该节点未访问过
		{
			printf("%c ", G->ver[i]);
			visited[i] = true;
			EnQueue(&Q,i);//访问该节点后，将该节点入队
			while (!QueueEmpty(Q))
			{
				DeQueue(&Q, &i);//拿出队头元素，开始找它的临接点来遍历
				for (j = 0; j < G->numv; j++)
				{
					if (G->edge[i][j] != MAXSIZE && !visited[j])//找没有遍历过的邻接点
					{
						printf("%c ", G->ver[j]);
						visited[j] = true;
						EnQueue(&Q, j);//访问该节点后，将该节点入队
					}
				}
			}

		}
	}
}

广度优先搜索代码实现：（基于邻接表）

void BFS(GraphAdjList *GL)
{
	int i;
	Queue Q;
	for (i = 0; i < GL->numv; i++)
	{
		visited[i] = false;
	}
	IniQueue(&Q);
	for (i = 0; i < GL->numv; i++)
	{
		visited[i] = true;
		printf("%c", GL->adjList[i].data);
		EnQueue(&Q, i);
		while (!QueueEmpty)
		{
			DeQueue(&Q, &i);
			EdgeNode* p = GL->adjList[i].firstedge;
			while (p)
			{
				if (!visited[p->adjvex])
				{
					visited[p->adjvex] = true;
					printf("%c ", GL->adjList[p->adjvex]);
					EnQueue(&Q, p->adjvex);
				}
				p = p->next;
			}
		}
	}
}

本章结束。