深度优先搜索算法是一种图的搜索算法。深度优先搜索采用的策略是,尽可能地访问相邻结点,访问到底之后就往回退出,直至栈被清空。
题目是这样子的
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B
为此,我们就根据上面的思路来实现。可以使用标准库的stack来保存“仍在搜索中的结点”。这里采用的是邻接矩阵法来表示图,以此实现深度优先搜索。
深度优先搜索的具体操作
1、把搜索的起点压入堆栈
2、循环进行以下的操作:
(1)访问栈顶的结点u
(2)如果栈顶的结点u还有未被访问的子结点,就访问他们(结点id较小的优先被访问),当结点u没有未被访问的子结点的时候,就将结点u从堆栈中弹出
标记每个结点的状态
为了标记每个结点当前的状态,我们可以用三种颜色来描述他们的状态:
白色->未被访问
灰色->正在被访问中
黑色->已经访问结束
下面有个图片很具体的描述了深度优先搜索的过程
分析
使用邻接矩阵的深度优先搜索算法,由于程序要调查每个顶点是否与其他每个顶点相邻,因此时间复杂度为O(n²)。并且,对于规模较大的图,还可能导致堆栈溢出。
用堆栈实现的深度优先搜索
#include<iostream>
#include<stack>
using namespace std;
#define MAX 100
#define WHITE 0
#define GRAY 1
#define BLACK 2
int n;
int d[MAX+1],f[MAX+1];//进入时间和退出时间
int M[MAX+1][MAX+1];
int color[MAX+1];
int tt=0;
int nt[MAX+1];//用来存放当前结点访问到的是第几个子结点
int next(int u)
{
for(int v = nt[u];v<=n;v++)
{
nt[u] = v+1;
if(M[u][v]) return v;
}
return -1;
}
void dfs_visit(int r)
{
for(int i=0;i<=n;i++)
nt[i] = 0;
stack<int>S;
S.push(r);
color[r] = GRAY;
d[r] = ++tt;
while(!S.empty())
{
int u = S.top();
int v = next(u);
if(v!=-1)
{
if(color[v]==WHITE)
{
color[v] = GRAY;
d[v] = ++tt;
S.push(v);
}
}
else
{
S.pop();
color[u] = BLACK;
f[u] = ++tt;
}
}
}
void dfs()
{
for(int i=0;i<=n;i++)
color[i] = WHITE;
tt = 0;
//以未访问的结点u为起点进行深度优先搜索。
for(int u=1;u<=n;u++)
{
if(color[u] == WHITE) dfs_visit(u);
}
for(int i=1;i<=n;i++)
{
cout<<i<<" "<<d[i]<<" "<<f[i]<<endl;
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
int u,k;
cin>>u>>k;
for(int j=0;j<k;j++)
{
int v;
cin>>v;
M[u][v] = 1;
}
}
dfs();
}