6.2 BFS与DFS

广度优先搜索(BFS)
自顶点s的广度优先搜索(Breadth-First Search)
(1) 访问顶点s
(2) 依次访问s所有尚未访问的邻接顶点
(3) 依次访问以上被访问过顶点的尚未访问的邻接顶点
(4) 如此反复，直至没有尚未访问的邻接顶点

template <typename Tv, typename Te> // 顶点类型、边类型
void Graph<Tv, Te>::BFS(int v, int & clock) {
    Queue<int> Q;
    status(v) = DISCOVERED;
    Q.enqueue(v); // 初始化
    while (!Q.empty()) {
        int v = Q.dequeue();
        dTime(v) = ++clock; // 取出队首顶点v
        for (int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) { // 考察v的每一个邻接顶点u
            if (UNDISCOVERED == status(u)) { // 若u尚未被发现
                status(u) = DISCOVERED;
                Q.enqueue(u); // 发现该顶点
                status(v, u) = TREE;
                parent(u) = v; // 引入树边
            } else { // 若u已被发现（正在队列中），或已访问完毕（已出队列）
                status(v, u) = CROSS; // 将(v, u)归类于跨边
            }
        }
        status(v) = VISITED; // 当前顶点访问完毕
    }
}

template <typename Tv, typename Te> // 顶点类型、边类型
void Graph<Tv, Te>::bfs(int s) { // s为起始顶点
    reset();
    int clock = 0;
    int v = s; // 初始化
    do { // 逐一检查所有顶点，一旦遇到尚未发现的顶点
        if (UNDISCOVERED == status(v))
            BFS(v, clock); // 即从该顶点出发启动一次BFS
    } while (s != (v = (++v % n))); // 按序号访问，不漏不重
}

深度优先搜索(DFS)
自顶点s的深度优先搜索(Depth-First Search)
(1) 访问顶点s
(2) 若s尚有未被访问的邻居，则任取一u，递归执行DFS(u)
(3) 否则，返回

template <typename Tv, typename Te> // 顶点类型、边类型
void Graph<Tv, Te>::DFS(int v, int & clock) {
    dTime(v) = ++clock;
    status(v) = DISCOVERED; // 发现当前顶点v
    for (int u = firstNbr(v); -1 < u; u = nextNbv(v, u)) { // 枚举v的每一个相邻顶点u
        switch(status(u)) { // 视其状态分别处理
            case UNDISCOVERED: // u尚未发现，意味着支撑树可在此拓展
                status(v, u) = TREE;
                parent(u) = v;
                DFS(u, clock);
                break; // 递归
            case DISCOVERED: // u已被发现但尚未访问完毕，应属被后代指向的祖先
                status(v, u) = BACKWARD;
                break;
            default: // u已访问完毕，视承袭关系分为前向边或跨边
                status(v, u) = dTime(v) < dTime(u) ? FORWARD : CROSS;
                break;
        }
    }
    status(v) = VISITED;
    fTime(v) = ++clock; // 至此，当前顶点v访问完毕
}

顶点的活动期 active[u] = (dTime[u], fTime[u])
括号引理(Parenthesis Lemma)：给定有向图G = (V, E)及其任一DFS森林，则
u是v的后代 iff active[u] ⊆ active[v]
u是v的先代 iff active[u] ⊇ active[v]
u与v无关 iff active[u] ∩ active[v] = Ø