图的BFS和DFS

广度优先搜索

如图所示：是一个有向图的广度遍历过程。

广度优先搜索.png

/* 定义边的遍历状态 和边的种类 */
typedef enum { UNDISCOVERED, DISCOVERED, VISITED } VStatus;

/* s作为遍历的起点 */
void Graph::bfs(int s) {
    /* 重置所有顶点的遍历状态(UNDISCOVERED) */
    reset();

    /* 初始化记录遍历路径的parent数组 */
    parent.resize(n);
    for (int i = 0; i < n; i++)
        parent[i] = -1;

    int v = s;
    do
        if (status(v) == UNDISCOVERED)
            BFS(v);
    while( s != (v = (++v % n)) );
}

/* 广度优先搜索算法（单个连通域）*/
void Graph::BFS(int v) {
    std::queue<int> queue;
    
    status(v) = DISCOVERED;
    queue.push(v);

    while(!queue.empty()) {
        int v = queue.front();
        queue.pop();

        for (int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) {
            if (UNDISCOVERED == status(u)) {
                parent[u] = v;  /* 记录遍历的父节点 */
                queue.push(u);
                status(u) = DISCOVERED; /* 更新顶点的遍历状态 */
            }
            status(v) = VISITED;
        }
    }
}

/* 顶点i中相对于顶点j的的下一邻接点 */
int nextNbr(int i, int j) {
    while(  (-1 < --j) && !(existEdge(i, j)) )
        ;
    return j;
}

复杂度

除了作为输入的图本身外，BFS搜索所使用的空间，主要消耗在用于维护顶点访问次序的辅助队列，用于记录顶点和边状态的标识位向量。累计O(n) + O(n) +O(e) = O(n+e)

在时间方面，bfs本身对所有顶点的枚举供需要O(n)时间，而在BFS()的调用中，每个顶点，每条边均只耗费O(1)时间，累计O(n+e)。综合起来，总体是O(n+e)

深度优先搜索

深度优先搜索选取下一顶点的关键策略，可概括为：优先选取最后一个被访问到的顶点的邻居

于是，以顶点s为基点的DFS搜索，将首先访问顶点s；再从s所有尚未访问到的邻居中任取其一，并以此为基点，递归的执行DFS搜索。故各顶点的访问次序类似于树的先序遍历；

1.png 2.png 3.png

/* 定义边的遍历状态 和边的种类 */
typedef enum { UNDISCOVERED, DISCOVERED, VISITED } VStatus;

void Graph::dfs(int s)
{
    /* 重置所有顶点的遍历状态 */
    reset();

    /* 初始化记录遍历路径的parent数组 */
    parent.resize(n);
    for (int i = 0; i <= n; i++)
        parent[i] = -1;

    /* 逐一检查所有顶点 */
    int v = s;
    do
        if (UNDISCOVERED == status(v))    // 一旦遇到尚未发现的顶点
            DFS(v);    // 即从该定点出发启动一次DFS
    while(s != (v = (++v % n)));    // 按序号检查，不重不漏
}

/* 深度优先搜索DFS算法(单个连通域) */
void Graph::DFS(int v) {
    status(v) = DISCOVERED;

    for (int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) {
        if (status(u) == UNDISCOVERED) {
            parent[u] = v;
            DFS(u);
        }
    }
    status(v) = VISITED;
}

算法的实质功能，由子算法DFS()递归完成。每一递归实例中，都先将当前节点v标记为DISCOVERED(已发现)状态，再逐一核对其各邻居u的状态并做相应处理。待其所有邻居均已处理完毕之后，将顶点v置VISITED(访问完毕)，便可回溯。

若顶点u尚处于UNDISCOVERED(未发现)状态，则将边(v, u)归类为树边，并将v记作u的父节点。然后将u作为当前节点，继续递归遍历。(若顶点u处于DISCOVERED状态，则意味着在此处发现一个有向回路)