算法与数据结构之深度优先搜索

深度优先搜索算法是一种图的搜索算法。深度优先搜索采用的策略是，尽可能地访问相邻结点，访问到底之后就往回退出，直至栈被清空。

题目是这样子的

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();


}

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~