【数据结构】图的遍历

文章目录

• 引言
• 一、深度优先遍历
• • 1.1 定义
  • 1.2 实现
• 二、广度优先遍历
• • 2.1 定义
  • 2.2 实现
• 三、DFS与BFS的对比

引言

前置知识：【数据结构】图的概念和存储结构

一、深度优先遍历

1.1 定义

深度优先遍历（Depth First Search，DFS），是一种从某个顶点开始，沿着一条路径不断深入到未访问的顶点，直到没有新的顶点可以访问为止。然后回溯到前一个顶点，再继续访问其他未被访问的顶点，直到所有顶点都被访问到。

1.2 实现

思路：

1. 创建vis数组，用于标记已遍历过的顶点，初始为false。
2. 由于DFS需要递归展开，所以分出一个子函数_DFS。
3. 进入子函数代表已到达src，所以将vis[srci]标记为true。
4. 随后for循环查找与当前点相连且没被遍历过的点，再次以新点作为当前点进入子函数，构成重复子问题。
5. _DFS调用完后，再检查vis数组是否还有未被遍历的点。若有，则再次以此点进行_DFS，防止不连通的区域未被遍历。

void _DFS(int srci, vector<bool>& vis)
{
	vis[srci] = true;
	cout << "[" << srci << "]" << ":" << _vertexs[srci] << endl;

	for (int i = 0; i < _vertexs.size(); ++i)
	{
		if (_edges[srci][i] != W_MAX && !vis[i])
		{
			_DFS(i, vis);
		}
	}
}

void DFS(const V& src)
{
	int n = _vertexs.size();
	vector<bool> vis(n, false);

	int srci = GetIndex(src);
	_DFS(srci, vis);

	//防止不连通的区域未被遍历
	for (int i = 0; i < n; ++i)
	{
		if (!vis[i])
		{
			_DFS(i, vis);
		}
	}
}

细节：vis数组的作用，是为了保证遍历的过程中，不遍历相同的点，防止算法时间复杂度大大增加，导致冗余计算。利用vis数组不去遍历相同的点，这个过程又称为剪枝。

二、广度优先遍历

2.1 定义

广度优先遍历（Breadth First Search, BFS），是一种从某个顶点开始，先访问当前顶点的所有邻接顶点，然后再依次访问这些邻接顶点的邻接顶点。BFS 是逐层遍历的过程，优先访问离起点较近的顶点。

2.2 实现

思路：

1. 创建vis数组，用于标记已遍历过的顶点，初始为false。
2. 创建队列，用于存储待访问的顶点下标。
3. 初始化，将源点下标存入队列，vis中标记为true。
4. while循环中，每次取出队头数据并弹出，随后for循环查找与当前点相连且没被遍历过的点，将其存入队列，并且vis中标记为true，构成重复子问题。

void BFS(const V& src)
{
	int n = _edges.size();
	vector<bool> vis(n, false);
	queue<int> q;

	int srci = GetIndex(src);
	q.push(srci);
	vis[srci] = true;

	int levelSize = 1;
	while (!q.empty())
	{
		//每层分行打印
		for (int i = 0; i < levelSize; ++i)
		{
			int front = q.front();
			q.pop();
			cout << "[" << front << "]" << ":" << _vertexs[front] << " ";

			for (int j = 0; j < n; ++j)
			{
				if (_edges[front][j] != W_MAX && !vis[j])
				{
					q.push(j);
					vis[j] = true;
				}
			}
		}
		cout << endl;

		levelSize = q.size();
	}
}

细节：levelSize的设置，是为了按源点的度从小到大分层打印。每次while循环里用for循环控制打印换行，随后更新levelSize。看似增加一套循环，实际并没有增加时间复杂度。

三、DFS与BFS的对比

以下是 深度优先遍历（DFS） 和 广度优先遍历（BFS） 的对比表格：

• V 是图中的顶点数，E 是图中的边数。