无向图

在进行BFS的时候，要对进行分层处理。注意的是这里使用的是queue.

如果起点是A的话，第一层是A, 第二层是 B C，第三层是 D E，第四层是 F， 是一种逐渐向外扩散的过程，这种对于找最短路径来说是非常有帮助的算法。

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

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

void bfs_viewer(const char_graph_type& gp, char st)
{
    std::set<char> used_vertex;  //使用过的顶点容器
    std::queue<char> vertex_queue; //待使用的顶点容器
    vertex_queue.push(st);

    while(!vertex_queue.empty())
    {
        auto item = vertex_queue.front();
        vertex_queue.pop();

        if(used_vertex.find(item) == used_vertex.end())
        {
            std::cout << item << ' '; //打印当前的顶点
            auto child_vertexes = gp.at(item); //获取当前点的子顶点
            std::for_each(child_vertexes.begin(), child_vertexes.end(),
                          [&vertex_queue](char c){vertex_queue.push(c);}); //未使用过的子顶点，添加到队列中
        }
        else
        {
            //当前顶点被使用过，什么都不做
        }
        used_vertex.insert(item); //插入当前的顶点到使用过的顶点集合中
    }
    std::cout << '\n';
}

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)
    {
        bfs_viewer(gp, c);
    
}

软件运行的结果，打印输出：

程序运行结果