无向图及其深度优先搜索和广度优先搜索

无向图

图（Graph）是表示事物与事物之间的关系的数学对象，是数学领域的重要分支——图论（Graph Theory）的研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。无向图中边（edge）仅仅是两个顶点（vertex）之间的连接，是比较简单的图。

我们定义无向图的结构如下（这里我选择用邻接表来表示无向图）：

#include <map>
#include <forward_list>

using namespace std;

struct UndirectedGraph
{
    size_t V, E; //V表示顶点数，E表示边数
    map<int, forward_list<int>> adj;
};

深度优先搜索

 深度优先搜索（Depth First Search，DFS）是图论的重要算法，它的思想是从某一个顶点出发向其邻近顶点移动（不能重复访问顶点），直至找到目标或已经无法继续深入。深度优先遍历的结束标志则是从起点出发能到达的所有顶点都已经被访问过，即结合回溯法来遍历。对于遍历，如果图是连通的，每个邻接表中的元素都会被访问到。深度优先遍历中得到的每一条路径都是图的一个连通分量，因此深度优先搜索常用来解决连通分量的计算问题。

下面是深度优先遍历的源码示例：

void dfs(UndirectedGraph &graph, vector<int> &visited, int v)
{
    visited[v] = 1;
    cout << v << " ";
    for (const int &i : graph.adj.at(v))
    {
        if (!visited[i])
        {
            dfs(graph, visited, i);
        }
    }
}

非递归版本用后进先出（LIFO）的栈来保存已经访问过的顶点，当深入到无路可走时便弹出栈元素，在新的栈顶上继续进行遍历。

void dfs(Undirected &graph, vector<int> &visited, int v) {
    if (visited[v] == 1)
    {
        return ;
    }
    cout << v << " ";
    stack<int> st;
    st.push(v);
    while (!st.empty())
    {
        int i = st.top();
        forward_list<int>::const_iterator ite;
        for (ite = graph.adj.at(i).cbegin(); ite != graph.adj.at(i).cend(); ++ite)
        {
            if (!visited[*ite])
            {
                cout << *ite << " ";
                visited[*ite] = 1;
                st.push(*ite);
                break;
            }
        }
        if (ite == graph.adj.at(i).cend())
        {
            st.pop();
        }
    }
}

 广度优先搜索

广度优先搜索（Breadth First Search，BFS）是在遍历完当前顶点的所有相邻顶点后才会转到下一层顶点去遍历。广度优先搜索常用于寻找最短路径。

void bfs(UndirectedGraph &graph, vector<int> &visited, int v)
{
    queue<int> q;
    visited[v] = 1;
    cout << v << " ";
    q.push(v);
    while (!q.empty())
    {
        int tmp = q.front();
        q.pop();
        for (int i : graph.adj.at(tmp))
        {
            if (!visited[i])
            {
                cout << i << " ";
                visited[i] = 1;
                q.push(i);
            }
        }
    }
}