1. 广度优先遍历

在深度优先遍历中，从一个节点出发然后一直递归的去遍历和它相连的节点，也就是说我们是依次遍历完成一个节点的子图。 广度优先遍历不同于深度优先遍历，我们从一个节点出发遍历完和它相连的节点，然后再去遍历和它相连的这些节点相连的节点，就好像是一层层的去遍历完整个图（和二叉树的层序遍历类似）。 还是从一个例子出发：

广度优先遍历

2. 代码实现

class GraphBFS
{
public:
    GraphBFS(Graph& g):g(g){};
    ~GraphBFS(){}
    void printLine()
    {
        std::cout << "BFS res: " << std::endl;
        for (auto i : res)
            std::cout << i << " ";
        std::cout << std::endl;
    }
    void BFS()
    {
        visited = std::vector<bool>(g.m_nV, false);
        std::queue<int> q;
        q.push(0);
        visited[0] = true;
        while (!q.empty())
        {
            int cur = q.front();
            q.pop();
            
            res.push_back(cur);
            for (auto i : g.adj(cur))
            {
                if (!visited[i])
                {
                    q.push(i);
                    visited[i] = true;
                }
            }
        }
    }
private:
    std::vector<int> res;
    Graph& g;
    std::vector<bool> visited;
};

3. 广度优先遍历的应用

一般而言，能使用深度优先遍历解决的问题也可以使用广度优先遍历来进行解决。深度优先遍历可以使用递归让代码显得比较简洁，但是深度优先遍历没办法使用递归进行编写。所以可以看到在很多情况下也会使用深度优先遍历求解问题。我们继续上一篇中的几个应用，尝试使用广度优先遍历的方法来解决他们。

3.1 无向图的联通分量

class CCBFS
{
public:
    CCBFS(Graph& g) : g(g){}

    void bfs(int id, int cc)
    {
        std::queue<int> q;
        q.push(id);
        visited[id] = true;
        while (!q.empty())
        {
            int v = q.front();
            q.pop();

            for (auto w : g.adj(v))
            {
                if (!visited[w])
                {
                    q.push(w);
                    visited[w] = true;
                }
            }
        }
    }

    int getCount()
    {
        int cc = 0;
        visited = std::vector<bool>(g.m_nV, false);
        for (size_t i = 0; i < g.m_nV; i++)
        {
            if (!visited[i])
            {
                bfs(i, cc);
                cc++;
            }
        }
        return cc;
    }

private:
    Graph& g;
    std::vector<bool> visited;
};

3.2 路径问题

class SingleSourcePathBFS
{
public:
    SingleSourcePathBFS(Graph &g, int s) :g(g) {
        pre = std::vector<int>(g.m_nV, -1);
        visited = std::vector<bool>(g.m_nV, false);
        srcV = s;
        bfs(s);
    }

    std::vector<int> path(int dst) {
        std::vector<int> res;
        int cur = dst;
        while (cur != srcV) {
            res.push_back(cur);
            cur = pre[cur];
        }
        res.push_back(cur);
        std::reverse(res.begin(), res.end());
        return res;
    }
private:
    Graph& g;
    int srcV;
    std::vector<int> pre;
    std::vector<bool> visited;

    void bfs(int s) {
        std::queue<int> q;
        q.push(s);
        visited[s] = true;
        pre[s] = s;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto w : g.adj(v)) {
                if (!visited[w]) {
                    q.push(w);
                    visited[w] = true;
                    pre[w] = v;
                }
            }
        }
    }
};

广度优先遍历求解无向图的路径时有一个特别重要的性质：求解的结果是最短路径，所以在有些问题中要求解最短路径只能使用广度优先遍历，不能使用深度优先遍历。

3.3 检测无向图中的环

class CycleDetectionBFS
{
public:
    CycleDetectionBFS(Graph &g) : g(g) {
        visited = std::vector<bool>(g.m_nV, false);
        pre = std::vector<int>(g.m_nV, -1);
        bHasCycle = false;
        for (size_t v = 0; v  < g.m_nV; ++v){
            if (visited[v] == false && bfs(v)){
                bHasCycle = true;
                break;
            }
        }
    }
    bool hasCycle(){
        return bHasCycle;
    }
private:
    Graph &g;
    std::vector<bool> visited;
    std::vector<int> pre;
    bool bHasCycle;
    bool bfs(int v) {
        std::queue<int> q;
        q.push(v);
        visited[v] = true;
        pre[v] = v;
        while (!q.empty())
        {
            int k = q.front();
            q.pop();
            for (auto w : g.adj(k)){
                if(!visited[w]){
                    q.push(w);
                    visited[w] = true;
                    pre[w] = k;
                }
                else if(w != pre[k]){
                    return true;
                }
            }
        }
        return false;
    }
};

3.4 二分图检测

class BipartitionDetectionBFS
{
public:
    BipartitionDetectionBFS(Graph &g) : g(g) {
        visited = std::vector<bool>(g.m_nV, false);
        colors = std::vector<int>(g.m_nV, -1);
        isBipartite = true;
        for (size_t v = 0; v < g.m_nV; ++v) {
            if (visited[v] == false){
                if (!bfs(v, 0)) {
                    isBipartite = false;
                    break;
                }
            }
        }
    }
private:
    Graph& g;
    std::vector<bool> visited;
    std::vector<int> colors;
    bool isBipartite;
    bool bfs(int v, int color) {
        std::queue<int> q;
        q.push(v);
        visited[v] = true;
        colors[v] = color;
        while (!q.empty())
        {
            int k = q.front();
            q.pop();
            for (auto w : g.adj(k))
            {
                if (!visited[w]){
                    q.push(w);
                    visited[w] = true;
                    colors[w] = 1 - colors[k];
                }
                else if(colors[w] == colors[k])
                    return false;
            }
        }
        return true;
    }
};

4 DFS vs. BFS

对比dfs和bfs的结构： img 从上图中可以看到他们的结构基本上都是一模一样的，除了使用暂存的数据结构的不同，其余都是一样的。那么我们可以使用其他的数据结构来进行遍历吗？**可以！**而且我们可以使用随机的存储结构来进行遍历。