盲目搜索 – DFS思想及应用

DFS理解

DFS将问题抽象为状态与相邻状态之间的关系

利用系统栈完成递归调用

调用展开结构是相邻节点数量为n的 n叉递归树

利用调用轨迹可用于图相关算法和枚举

DFS算法概要

    void DFS(Node &n) {
        for(Node &x: n -> neighbors) {
            if(visited_set[x].count() <= 0) {
                visited_set.insert(x);
                DFS(x);
            }
        }
    }

DFS非递归实现

DFS判断连通性

    ...
    DFS(start, target);
    ...

    void DFS(Node &n, Node &target)
    {
        if(n == target)
            isConnected = true;
        for...
    }

DFS利用栈记录连通路径

    ...
    for(Node &start: graph)
        if(visited_set.count(start) <= 0)
            DFS(start, target);
    ...

    void DFS(Node n, Node &target)
    {
        path_vector.push_back(n);
        visited_set.insert(n);

        if(n == target)
        {
            isConnected = true;
            print(path_vector);
            path_vector.pop_back();
        }

        for(Node &x: n->neighbors)
            if(visited_set.count(x) <= 0)
                DFS(x, target);

        path_vector.pop_back();
    }

DFS利用树记录连通路径

    ...
    for(Node &start: graph)
        if(visited_set.count(start) <= 0)
            DFS(start, target);
    ...

    void DFS(Node &n, Node &target)
    {
        if(n == target)
        {
            for(Node x = n; x != start; x = root_map[x])
                tmp_stack.push();

            for(!tmp_stack.empty())
            {
                print(tmp_stack.top());
                tmp_stack.pop();
            }
        }

        for(Node &x: n -> neighbors)
        {
            if(visited_set.count(x) <= 0)
            {
                root_map[x] = n;
                DFS(x, target);
            }
        }
    }

DFS求连通分量个数

    ...
    for(Node &start: graph)
        if(visited_set.count(start) <= 0)
        {
            DFS(start);
            count++;
        }
    ...

    void DFS(Node &n)
    {
        for(Node &x: n -> neighbors)
            if(visited_set.count(x) <= 0)
                DFS(x);
    }

DFS求连通分量中元素个数

    ...
    for(Node &start: graph)
        if(visited_set.count(start) <= 0)
        {
            int i = 0;
            DFS(start, i);
            count_vector.push_back(i);
        }
    ...

    void DFS(Node &n, int &i)
    {
        i++;
        for(Node &x: n -> neighbors)
            if(visited_set.count(x) <= 0)
                DFS(x, i);
    }

DFS判断是否无向有环图

    ...
    for(Node &start: graph)
        if(visited_set.count(start) <= 0)
            DFS(start, start);
    ...

    void DFS(Node &n, Node &nRoot)
    {
        for(Node &x: n -> neighbors)
        {
            if(visited_set.count(x) <= 0)
                DFS(x, n);

            else if(x != nRoot)
                hasCycle = true;
        }
    }

DFS判断是否二分图

    ...
    for(Node &start: graph)
        if(visited_set.count(start) <= 0)
            DFS(start);
    ...

    void DFS(Node &n)
    {
        for(Node &x: n -> neighbors)
        {
            if(visited_set.count(x) <= 0)
            {
                x -> color = ! n -> color;
                DFS(x);
            }

            else if(n -> color == x -> color)
                isBipartite = false;
        }
    }

DFS实现拓扑排序

• 拓扑排序

将有向图输出为序列，该序列满足图中的所有前驱节点一定排在其后继结点之前

• 思想分析

节点 \scriptsize cur 为根节点的图 \scriptsize G(cur)，其前序遍历或后序遍历的倒序一定是拓扑序列

问题是遍历整张图时，不一定能保证前序节点先访问：如图 \scriptsize G(pre) = pre \rightarrow G(cur)，可能先访问到后继节点 \scriptsize cur 执行子图 \scriptsize G(cur) 遍历，后访问到前驱节点 \scriptsize pre，此时破坏了拓扑顺序。因此前序遍历策略仅保证子图的访问是拓扑序列，不保证全图的访问顺序满足前序关系

但注意到一个性质：先访问到后继节点 \scriptsize cur 时，\scriptsize G(cur) \rightarrow pre 的倒序是 \scriptsize G(pre) = pre \rightarrow G(cur) 的拓扑序；先访问到前序节点 \scriptsize pre 时，后序遍历的倒序是 \scriptsize G(pre) = pre \rightarrow G(cur) 的拓扑序。综上得出，采用后序遍历策略时，倒序序列一定是全图的拓扑序，与节点的访问顺序无关

    ...
    for(Node &node: graph)
        if(visited_set.count(node) <= 0)
            DFS(node);

    for(int i = sort_vector.size(); i >= 0; i--)
        print(sort_vector[i]);
    ...

    void DFS(Node &n)
    {
        for(Node &x: n -> neighbors)
            if(visited_set.count(x) <= 0)
                DFS(x);

        sort_vector.push_back(n);
    }