C++：图的遍历

2024-10-07 16:32:27

一、简介

图的遍历通常有深度优先遍历和广度优先遍历两种方式，这两种遍历次序对无向图和有向图都使用。

本文分别介绍基于邻接矩阵和邻接表的图的深度优先遍历和广度优先遍历，对于邻接矩阵和邻接表不熟悉的可翻阅：C++：图的存储结构及实现

DFS和BFS的比较：

二、深度优先遍历

深度优先遍历也叫深度优先搜索（DFS），类似于树的前序遍历。DFS的基本思想是：

从某个顶点v开始，访问v。
从v的未被访问的邻接点中选取一个顶点w，然后从w出发进行DFS。
重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。

图的DFS的应用：

寻找路径：DFS常被用于寻找图中是否存在一条从起点到终点的路径。这适用于无权图的路径搜索，或需要找到所有路径的场景。
检测连通分量：DFS可以用于在无向图中检测图中的连通分量，即通过 DFS 可以找到所有与某一节点连通的节点。
拓扑排序：对于有向无环图，DFS 可以用于拓扑排序，这在任务调度和依赖关系排序问题中非常有用。
检测图中的环：在有向图中，DFS 可以用来检测是否存在环。通过检测 DFS 的回边，可以判断是否存在环。

基于邻接矩阵的图的DFS：

/*已知图的顶点数vertexNum、一维顶点数组vertex、二维邻接矩阵edge*/
void DFS(int v)
{
	vector<bool> visited(vertexNum,false);  //存储访问状态
	visited[v] = true;                      //标记该点为已访问
	cout << vertex[v];                      //对访问到的点执行相应操作
	for (int i = 0; i < vertexNum; i++)     //遍历每个顶点
	{
		if (edge[v][i] == 1 && !visited[i]) //v到该顶点有通路且该顶点未被访问
		{
			DFS(i);                         //从该点开始继续深度优先遍历
		}
	}
}

基于邻接表的图的DFS：

/*已知图的顶点数vertexNum、邻接表的相关信息*/
void DFS(int v)
{
	vector<bool> visited(vertexNum, false);
	int j;
	EdgeNode* p = nullptr;          //p作为工作指针
	visited[v] = true;              //标记该点已被访问
	cout << adjlist[v].vertex;      //对该点执行相关操作
	p = adjlist[v].firstEdge;       //p指向顶点v的边表
	while (p != nullptr)
	{
		j = p->adjvex;
		if (!visited[j])
		{
			DFS(j);
		}
		p = p->next;
	}
}

三、广度优先遍历

广度优先遍历也叫广度（宽度）优先搜索（BFS），类似于树的层序遍历。BFS的基本思想是：

从某个顶点v开始，访问v。
依次访问v的各个未被访问的邻接点v1、v2、... 、vk。
分别从v1、v2、... 、vk出发依次访问它们未被访问的邻接点，直至图中所有与顶点v有路径相通的顶点都被访问到。

图的BFS的应用：

最短路径搜索：BFS可以用来在无权图中找到从起点到终点的最短路径。这是因为它逐层扩展，保证了在找到目标节点时，路径是最短的。
搜索引擎中的网页爬虫：搜索引擎的爬虫通常使用 BFS 来遍历网络。BFS 可以确保爬虫首先抓取到距离当前网页“最近”的网页，从而逐步扩展覆盖整个互联网。
分层搜索：BFS 的逐层搜索特性可以帮助找到某个层次的所有节点。这种分层搜索在许多现实问题中非常实用，尤其是当我们需要逐层分析某些结构时。
最小生成树：在无向图中，BFS 也是构建最小生成树的一种常见方式。尽管常用 Prim 或 Kruskal 算法，但 BFS 仍然可以帮助找到无权图中的最小生成树。

基于邻接矩阵的图的BFS：

/*已知图的顶点数vertexNum、一维顶点数组、二维邻接矩阵*/
void BFS(int v)
{
	vector<bool> visited(vertexNum, false);//存储访问状态
	int w, j, vector<int> que(vertexNum);  //采用顺序队列
	int front = -1, rear = -1;             //初始化队列
	
	visited[v] = true;                     //标记该点为已访问
	cout << adjlist[v].vertex;             //执行与该点相关的操作

	que[++rear] = v;                       //被访问的顶点入队
	while (front != rear)                  //当队列非空
	{
		w = que[++front];                  //取队头元素
		
		for (j = 0; j < vertexNum; j++)    //遍历每个节点
		{
			if (edge[w][j] == 1 && !visited[j])//若该节点与w节点有通路且未被访问
			{
				visited[j] = true;         //标记该节点未已访问
				cout << vertex[j];         //执行与该节点相关操作
				que[++rear] = j;           //将该节点入队
			}
		}
	}
}

基于邻接表的图的BFS：

/*已知图的顶点数vertexNum、邻接表的相关信息*/
void BFS(int v)
{
	vector<bool> visited(vertexNum, false);//存储访问状态
	int w, j, vector<int> que(vertexNum);  //采用顺序队列
	int front = -1, rear = -1;             //初始化队列
	EdgeNode* p = nullptr;                 //工作指针
	visited[v] = true;                     //标记该点为已访问
	cout << adjlist[v].vertex;             //执行与该点相关的操作

	que[++rear] = v;                       //被访问的顶点入队
	while (front != rear)                  //当队列非空
	{
		w = que[++front];
		p = adjlist[w].firstEdge;          //工作指针指向顶点v的边表
		while (p != nullptr)               //当该顶点的邻接点还未访问完
		{
			j = p->adjvex;
			if (!visited[j])               //若该点未被访问
			{
				visited[j] = true;         //标记该点为已访问
				cout << adjlist[j].vertex; //执行与该点相关的操作
				que[++rear] = j;           //队列元素-1
			}
			p = p->next;                   //工作指针指向下一个邻接点
		}
	}
}

码农公寓

一、简介

二、深度优先遍历

三、广度优先遍历

相关文章