美文网首页
6.2 BFS与DFS

6.2 BFS与DFS

作者: 月影追猎者 | 来源:发表于2020-07-21 15:15 被阅读0次

广度优先搜索(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] = Ø

相关文章

  • 6.2 BFS与DFS

    广度优先搜索(BFS)自顶点s的广度优先搜索(Breadth-First Search)(1) 访问顶点s(2) ...

  • 用Python实现树的BFS与DFS

    一、BFS与DFS简介 在理解动态规划、BFS和DFS一文中,已经集合具体例子,介绍了图的BFS与DFS。但是比较...

  • Binary Tree(2)

    BFS vs DFS for Binary Tree What are BFS and DFS for Binar...

  • DFS与BFS LeetCode 刷题小结(一)

    本节我们将汇总一些 LeetCode bfs与dfs相关的题。 关于深度优先搜索(DFS)和广度优先搜索(BFS)...

  • LeetCode 第104题:二叉树的最大深度

    1、前言 2、思路 采用 DFS 或者 BFS 都可以。 3、代码 DFS: BFS:

  • 133. Clone Graph 复制无向图

    bfs dfs

  • BFS和DFS

    DFS BFS

  • BFS与DFS

    广度优先遍历 (BFS) 类似树的层次遍历,首先访问起始顶点v,然后选取与v邻接的全部顶点w1,w2,…wn,进行...

  • DFS与BFS

    以先序遍历打印链表为例: 以中序遍历打印链表为例: 以后序遍历打印链表为例: 以层序遍历打印链表为例:

  • BFS与DFS

    1.什么是BFS,DFS BFS宽度优先搜索.一层一层搜索.把每行的结果存入到队列中,然后遍历求下一层.DFS深度...

网友评论

      本文标题:6.2 BFS与DFS

      本文链接:https://www.haomeiwen.com/subject/bdmbkktx.html