最小支撑树(Prim)算法

港控/mmm° 2023-07-18 14:14 8阅读 0赞

### 文章目录 ###

*   *   *  算法介绍
         *  代码实现

### 算法介绍 ###

*  学习记录
 *  `支撑树`
    
     *  覆盖原图的无环联通子图称作原图的一颗支撑树(生成树)
 *  `最小支撑树`
    
     *  成本最低的支撑树,而成本是各边权重的总和
 *  `割`
    
     *  顶点集V的任一非平凡子集和它的补集都构成一个割。
 *  `桥`
    
     *  如果边uv满足顶点u在子集，v在补集 则称边uv是割的跨越边，也叫做桥。
 *  `prim算法`
    
     *  `算法原理`
        
         *  最小支撑树总是采用连接每一割的最短桥
     *  `算法实现(贪心迭代)`
        
         *  每一步迭代之前假设已经得到了最小支撑树T的一颗子树T(k) = (V(k), E(k))， 将V(k)和补集视作一个割,找到这个割的最短桥 e(k) = (v, u)，然后扩展成更大的子树 T(k+1) = (V(k+1), E(k+1));
         *  最初的T(1) 只包含单个顶点不包含边,所以可以从图中任意选择

### 代码实现 ###

*  借鉴了优先级算法
 *  `每次T(k)扩充到T(k+1)的时候,可以将V(k)之外顶点u到V(k)的距离视作优先级,优先级更新函数就是更新新的邻接顶点的优先级,将优先级替换成对应边的权重`

// 每次T(k)扩充到T(k+1)的时候,可以将V(k)之外顶点u到V(k)的距离视作优先级,优先级更新函数就是更新新的邻接顶点的优先级,将优先级替换成对应的权重
    // 每次挑选优先级数最小的那个顶点 所以挑选出来权重最小的边
    template <typename Tv, typename Te> struct PrimPu()
    {
        virtual void operator() (Graph<Tv,Te> *graph, int v, int u){
            // 只针对v未发现的节点
            if (graph->status(u) != UNDISCOVER) {
                return;
            }
    
            // 更新父节点
            g->parent(u) = v;
    
            // 将当前顶点的优先级数更新成该边的权重
            if (graph->weight(v, u) <  graph->priority(u)) {
                graph->priority(u) = graph->weight(v, u);
            }
        }
    
    };
    
    
    
     // 优先级搜索算法
        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;
            }
        }