优先级算法

朴灿烈づ我的快乐病毒、 2023-07-17 15:46 10阅读 0赞

### 文章目录 ###

*   *   *  介绍
         *   *  实现源码

### 介绍 ###

*  学习记录
 *  `给所有顶点赋予不同的优先级数, 随着算法的推进不断调整, 每一步迭代选取的顶点都是当时优先级数最低的那个。`负责调整优先级的部分以函数对象形式实现

#### 实现源码 ####

// 优先级搜索算法
        template <typename PU> void pfs(int v, PU prioUpdater){
            // 重置图状态
            reset();
    
            // 时间标签
            int clock = 0;
            int s = v;
    
            // 遍历所有顶点
            do {
                // 所有未发现的顶点执行优先级搜索算法
                if (status(v) == UNDISCOVERED) {
                    PFS(v, prioUpdater);
                }
                
                // 迭代到下一顶点
                v = ++v%n;
            } while (s != v);
        }
    
        // 连通域 优先级搜索框架
        template <typename PU> void PFS(int v, PU prioUpdater) {
            // 更新顶点优先级,状态
            priority(v) = 0; // 最高优先级
            status(v) = VISITED;
    
            // 起点s加入遍历树中
            parent(s) = -1;
            
            // 遍历所有顶点
            while(true) {
                // 更新当前顶点的邻接顶点的优先级数和父级顶点
                for (int w = firstNbr(s); w > -1 ; w = nextNbr(s, w)) {
                    prioUpdater(this,s, w);
                }
                
                // 获取尚未加入遍历树中的所有顶点中优先级数最小的顶点
                int shortest = INT_MAX;
                for (int w =0; w < n ; w++) {
                    if (status(w) == UNDISCOVERED && priority(w) < shortest) {
                        shortest = priority(w);
                        s = w;
                    }
                }
                
                // TODO 自定义一些事情
                
                // 所有顶点都已经遍历过了
                if (status(s) == VISITED) {
                    break;
                }
                
                // 更新当前顶点的状态
                status(s) = VISITED;
                type(parent(s), s) = TREE;
            }
        }