二维容器进行图的DFS搜索和BFS搜索-C++STL模板

场景

小K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个(也有可能没有)参考文献的链接指向别的博客文章。小K 求知欲旺盛,如果他看了某篇文章,那么他一定会去看这篇文章的参考文献(如果他之前已经看过这篇参考文献的话就不用再看它了)。那么小K看了某篇文章后一定会看到哪些文章呢?

题源:查找文献-洛谷


算法过程

这是一个图的搜索问题,图的搜索有两种方式:

  • DFS(深度优先搜索)
  • BFS(广度优先搜索)

深度优先搜索:

利用先进后出的特点,先将开始访问的结点入栈,然后重复下面两个步骤:
1)访问栈顶元素,然后将它出栈
2)将栈顶结点指向的所有结点入栈
直到栈空或已经访问完所有结点,搜索结束。

广度优先搜索:

利用队列先进先出的特点,类似地,先将开始访问的结点入队,然后重复下面两个步骤:
1)访问队头元素,然后将它出队
2)将队头结点指向的所有结点出队
直到队空或已经访问完所有结点,搜索结束。

需求分析:

  • 所有结点仅访问一次,且必须访问从起始结点能访问到的全部结点
  • 如果访问一个结点后,下一步同时存在多个选择,则优先访问编号较小的结点
  • 结点数量不超过105,边数不超过106

数据表示:

邻接矩阵显然不太行,因为可能需要1010个元素的二维数组。邻接表是可以的,但由于需要优先访问编号较小的结点,所以我最终选择了以升序优先队列为元素的容器,类似于二维容器

vector< priority_queue<int,vector<int>,greater<int>>  > a;
vector<int> visit;		//标记结点是否已访问

问题描述

1. 重复访问一个结点

如在深度优先遍历中,我控制了已访问的元素不再入栈。

相关代码:

while(!a[t].empty()) {	//结点t相关结点(未访问的)入栈 
	if(visit[a[t].top()]==0)
		ss.push(a[t].top()); 
	a[t].pop(); }

在一些测试数据中,它确实完成了我所希望它做的事情。但是我们看一个简单的例子:

Alt

在这个例子中,访问结点2时,结点4就压入栈中了,接着要访问结点3,但此时结点4还未访问,所以结点4又入栈。这就可能导致对4的重复访问

解决方案:

改在出栈时判断结点是否已经访问

if(visit[t]==0) {
	cout<<t<<" "; visit[t]=1; visit[0]++; }

2. 非法访问内存

解决了上面的问题之后,程序运行又被告知非法访问内存了。

相关代码:

//----------广度优先遍历
while(visit[0]<n) {
	int t=q.front(); q.pop();
	if(visit[t]==0) {
		cout<<t<<" "; visit[t]=1; visit[0]++; }
	while(!aa[t].empty()) {
		q.push(aa[t].top());
		aa[t].pop(); } }

仔细观察外层循环的控制条件,发现只有在所有的结点都被访问过,循环才会停止。但是我当时忽略了一种可能:如果输入的图是非连通的呢?那么第二行队列q已经了,仍然会被要求返回队头元素并弹出队头。

解决方案:

while(visit[0]<n && !q.empty()) {

找到问题之后,处理问题反而挺简单了,仅仅加了个!q.empty()的判断条件。但是为什么不把前面visit[0]<n的判断条件去掉呢?
因为访问完所有结点后,队列还不一定为空呀!队列中可能还有已经访问过的结点,提前结束循环可以稍稍提高一点程序的效率。


最终源代码

#include<iostream>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
int main() {
	vector< priority_queue<int,vector<int>,greater<int>>  > a;
	queue<int> q;
	stack<int> s,ss;	//ss辅助 
	vector<int> visit;	//已访问结点记1,下标0记录已访问结点数 
	int n,m,x,y;		//x,y为x到y的一条边	
	cin>>n>>m;
	for(int i=0;i<=n;i++) {	//扩充结点,下标0不用 
		a.push_back(priority_queue< int,vector<int>,greater<int> >()); 
		visit.push_back(int()); }
	for(int i=0;i<m;i++) {	//输入边 
		cin>>x>>y;
		a[x].push(y); }
	vector< priority_queue<int,vector<int>,greater<int>>  > aa(a);	//因为a经过一次遍历后就空了 
	//----------深度优先遍历 
	s.push(1);
	while(visit[0]<n && !s.empty()) {	
		int t=s.top(); s.pop();	//t记录栈顶,待访问结点出栈 
		if(visit[t]==0) {
			cout<<t<<" "; visit[t]=1; visit[0]++; }	 
		while(!a[t].empty()) {	//t相关结点(未访问的)入栈 
			ss.push(a[t].top()); 
			a[t].pop(); }
		while(!ss.empty()) {	//入栈共两次,使最终出栈为升序 
			s.push(ss.top()); ss.pop(); } }
	cout<<endl;
	//----------广度优先遍历
	for(int i=0;i<=n;i++)
		visit[i]=0;
	q.push(1);
	while(visit[0]<n && !q.empty()) {
		int t=q.front(); q.pop();
		if(visit[t]==0) {
			cout<<t<<" "; visit[t]=1; visit[0]++; }
		while(!aa[t].empty()) {
			q.push(aa[t].top());
			aa[t].pop(); } }
	return 0; }
/*测试数据:
8 9
1 2
1 3
1 4
2 5
2 6
3 7
4 7
4 8
7 8
*/

运行:
在这里插入图片描述


文章看到这里就结束啦,你们的支持就是博主不断创作的动力!


原文连接:https://blog.csdn.net/m0_63238256/article/details/125450893

相关推荐

翟佳:高可用、强一致、低延迟——BookKeeper的存储实现

管正雄:基于预训练模型、智能运维的QA生成算法落地

814. 二叉树剪枝 : 简单递归运用题

【综合笔试题】难度 3.5\u002F5,多解法热门二叉树笔试题

【java刷算法】牛客—剑指offer3栈、数组、递归、二分法的初步练习

leetcode 2342. Max Sum of a Pair With Equal Sum of Digits (python)

22张图带你深入剖析前缀、中缀、后缀表达式以及表达式求值

随机数索引(一题双解)【Leetcode每日(4.25)一题】C++

1260. 二维网格迁移 : 简单构造模拟题

坚持用C++刷牛客题(剑指offer专题)

日拱一卒,麻省理工教你信息安全和密码学

C语言——三种方式实现学生信息管理

快速排序及优化

萌新也能看懂的KMP算法

简答一波 HashMap 常见八股面试题 —— 算法系列(2)

素数算法(Prime Num Algorithm)

必须收藏!双目立体匹配算法:Patch Match Stereo实用详解教程

有哪些高质量的自学网站?

731. 我的日程安排表 II : 线段树(动态开点)的两种方式

LeetCode周赛302,这也太卷了,20分钟ak也只有300名……