深度优先算法

╰+攻爆jí腚メ 2023-07-15 09:01 31阅读 0赞

### 文章目录 ###

*   *   *  介绍
         *  实现

### 介绍 ###

*  学习记录
 *  `优先选取最后一个被访问到的顶点的邻居, 而访问完毕顺序类似于后序遍历`
    
     *  首先访问顶点s,再从未访问的邻居中任选其一, 然后递归执行上述步骤, 直到被访问顶点没有邻接顶点, 此时这个顶点才算访问完毕
     *  `类似于树的后序遍历算法`

### 实现 ###

// 深度优先算法
        void dfs(int s) {
            // 初始化
            reset();
            int clock = 0;
            int v = s;
    
            do {
    
                if (status(v) == UNDISCOVERED) {
                    DFS(v, clock);
                }
    
                // 轮询各个顶点
                v = ++v % n;
            } while (s != v)
    
        }
    
        void DFS(int v, int &clock) {
            // 更新当前顶点的状态
            status(v) = DISCOVERED;
            dTime(v) = ++clock;
    
            // 轮询各个邻居顶点
            for (int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) {
                switch (status(u)) {
                    // 未发现
                    case UNDISCOVERED:
                        updateUndiscoveredVertex(u, v);
                        break;
                        // 已发现，但是未访问完毕此时u时v的祖先
                    case DISCOVERED:
                        // 后向边
                        type(v, u) = BACKWARD;
                        break;
                        // 已访问 可能是跨边，也可能时前向边
                    default:
                        type(v, u) = (dTime(v) < dTime(u)) ? FORWARD : CROSS;
    
                }
            }
    
            // 当前顶点没有了邻接顶点的时候
            status(v) = VISITED;
            fTime(v) = ++clock;
            // TODO 一些单元操作
        }
    
        // 更新未发现邻接节点
        void updateUndiscoveredVertex(int u, int v, int &clock) {
            // 更新遍历树中的状态
            parent(u) = v;
            type(v, u) = TREE;
            DFS(u, clock);
        }