广度优先算法

简介

很多问题可以抽象为图的问题，从图中寻找某个点，最通用的办法就是暴力穷举。而广度优先和深度优先是两种常用的遍历图的方法。以一个树状图来说，广度优先就是从根节点开始，一层一层的遍历，下一层的必须等上一层全部遍历完成才可以被访问。而以一个无向图来举例的话，通过下面的图来理解：

topo.png

S为起点
接下来遍历位于同一层次的A,B,C
再接下来遍历下一层次的D

所以顺序为S,A,B,C,D。

详解

那么具体的思路是什么呢？维护一个即将访问的队列，这个队列按层次顺序存放着即将被访问的节点。

首先S加入队列Q。
访问S，同时将S设置为已经被访问。
循环从Q中取出节点：
- 如果Q为空，则遍历结束。
- 如果Q不为空，则类似于S，将该节点设置为已经访问。同时将其子节点加入Q进行排队。要观察子节点是否已经被访问或者已经加入了队列Q，否则将出现死循环，或者重复遍历。

用C++实现

用bfs的方法遍历用邻接链表表示的图(这里我用的数据结构为嵌套的vector)：

void BFS(vector<vector<int>> topo) {  //邻接链表
    deque<int> Q;  //即将访问 
    vector<int> P;  //已经访问
    Q.push_back(0);  //加入初始节点
    while (!Q.empty()) {
        int temp = Q.front();
        Q.pop_front();  
        cout << temp << " ";  //取出并访问该节点
        P.push_back(temp);   // 加入已经访问集合
        for (auto each : topo[temp]) {
            if (find(P.begin(), P.end(), each) != P.end()
                || find(Q.begin(), Q.end(), each) != Q.end())  //确保还没有被访问
                continue;
            Q.push_back(each);
        }
    }
}

注意：在添加子节点到Q队列时，要保证子节点没有被访问且还没有在Q队列中。可以使用数组置位O(1)的方法来表示，我这样通过find函数反而浪费了时间。