广度优先算法

野性酷女 2023-07-15 05:59 7阅读 0赞

### 文章目录 ###

*   *   *  基本信息
         *  实现

### 基本信息 ###

*  学习日常
 *  `越早被访问到的顶点，其邻居越优先被选用`
    
     *  先访问顶点s,再依此访问未被访问到的邻居，再按照后者被访问的先后循序一次访问它们的邻居
     *  `和树的层次遍历相似`

### 实现 ###

// 广度优先算法
        void bfs(int s) {
            // 重置图关系
            reset();
    
            // 时间标签
            int clock = 0;
            int v = s;
    
            do {
                // 未发现状态的顶点,则进行一次广度优先算法的搜索
                if (UNDISCOVERED = status(v)) {
                    BFS(v, clock);
                }
                v = (++v % n);
            } while (s != v) // 循环所有顶点
        }
    
        // 连通域 广度优先算法
        void BFS(int v, int &clock) {
            // 引入辅助队列
            Queue<int> Q;
    
            // 更新当前顶点的状态
            status(v) = DISCOVERED;
    
            // 入队
            Q.enqueue(v);
    
            // 轮询当前顶点的邻接
            while (!Q.empty()) {
                // 出队
                int v = Q.dequeue();
    
                // 更新访问,轮询时间标签
                dTime(v) = clock++;
    
                // 轮询当前顶点的邻接顶点
                for (int u = firstNbr(v); u > -1; u = nextNbr(v, u)) {
                    // 当前邻接顶点尚未发现
                    if (status(u) == UNDISCOVERED) {
                        // 入队
                        Q.enqueue(u);
    
                        // 更新遍历树父子关系
                        parent(u) = v;
    
                        // 更新边关系
                        type(v,u) = TREE;
    
                        // 更新顶点状态
                        status(u) = DISCOVERED;
                    } else {
                        // DISCOVERED, VISITED状态的顶点归纳到跨边中
                        type(v, u) = CROSS;
                    }
                }
    
                // 访问，更新状态
                status(v) = VISITED;
                fTime(v) = clock;
                // TODO 执行访问动作
            }
        }