DFS（深度优先搜索）C++实现

无向图

在进行DFS的时候，进行逐步深入的搜索。注意的是这里使用的是stack.

如果起点是A的话，经过的路径是一个逐渐深入的过程 A -> C -> E -> D ->F ->B。

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>

template<typename T>
using graph_type = std::map<T, std::vector<T>>;
using char_graph_type = graph_type<char>;



void dfs_viewer(const char_graph_type& gp, char st)
{

    std::set<char> used_vertex;
    std::stack<std::pair<char, char>> vertex_stack;
    vertex_stack.push({st, ' '});
    std::vector<std::pair<char, char>> parent_vec;

    while(!vertex_stack.empty())
    {
        auto item = vertex_stack.top();
        vertex_stack.pop();

        if(used_vertex.find(item.first) == used_vertex.end())
        {
            std::cout << item.first <<' ';
            auto child_vertexes = gp.at(item.first);
            std::for_each(child_vertexes.begin(), child_vertexes.end(), 
                          [=, &vertex_stack](char c){vertex_stack.push({c,item.first});});
            parent_vec.push_back(item);
        }

        used_vertex.insert(item.first);
    }

    std::cout << '\n';

    for(auto &item : parent_vec)
    {
        //second is parent node, first is child node.
        std::cout << "(" << item.second << ", " << item.first<<")";
    }

}

int main()
{
    char_graph_type gp {{'A', {'B','C'}},
                        {'B',{'A','C','D'}},
                        {'C',{'A','B','D','E'}},
                        {'D',{'B','C','E','F'}},
                        {'E',{'C','D'}},
                        {'F',{'D'}}
                       };

    char c;
    while(std::cin>>c)
    {
        dfs_viewer(gp, c);
    }

}

运行的结果为：

运行结果