场景
小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(); }
在一些测试数据中，它确实完成了我所希望它做的事情。但是我们看一个简单的例子：
在这个例子中，访问结点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()) {
1
找到问题之后，处理问题反而挺简单了，仅仅加了个!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 */
运行：
