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

作者：阿锋

2022 年 9 月 02 日
湖南
本文字数：2089 字
阅读完需：约 7 分钟

@[TOC]

场景

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

题源：查找文献-洛谷

算法过程

这是一个图的搜索问题，图的搜索有两种方式：
DFS（深度优先搜索）
BFS（广度优先搜索）

深度优先搜索：

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

广度优先搜索：

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

需求分析：

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

数据表示：

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

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](https://img-blog.csdnimg.cn/6de035c5d9d143d7bda294e61ca53e83.jpeg#pic_center =300x)

在这个例子中，访问结点 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 91 21 31 42 52 63 74 74 87 8*/

复制代码

运行：

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

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/c026cecb220f7c399722f6b72】。文章转载请联系作者。

阿锋

关注

还未添加个人签名 2022.08.09 加入

还未添加个人简介

发布

暂无评论

创作场景

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

场景

算法过程

问题描述

1. 重复访问一个结点

2. 非法访问内存

最终源代码

阿锋

评论