当前位置：首页 > news >正文

最小支配集讲解

news 来源：原创 2024/5/3 10:26:33

定义

最小支配集:对于图G = (V, E) 来说,最小支配集指的是从 V 中取尽量少的点组成一个集合,

使得 V 中剩余的点都与取出来的点有边相连.也就是说,设 V' 是图的一个支配集,则对于图

中的任意一个顶点 u ,要么属于集合 V', 要么与 V' 中的顶点相邻. 在 V' 中除去任何元素后

V' 不再是支配集, 则支配集 V' 是极小支配集.称G 的所有支配集中顶点个数最少的支配集

为最小支配集,最小支配集中的顶点个数称为支配数.

求解

贪心策略:首先选择一点为树根,再按照深度优先遍历得到遍历序列,按照所得序列的反向序列的顺序进行贪心,对于一个即不属于支配集也不与支配集中的点相连的点来说,如果他的父节点不属于支配集,将其父节点加入到支配集.

伪代码:

　　第一步:以根节点深度优先遍历整棵树,求出每个点在深度优先遍历序列中的编号和每个点的父节点编号.

　　第二步:按照深度优先遍历的反向顺序检查每个点,如果当前点不属于支配集也不与支配集的点相连,且它的父节点不属于支配集,将其父节点加入到支配集,支配集中点的个数加 1, 标记当前节点, 当前节点的父节点, 当前节点的父节点的父节点,因为这些节点要么属于支配集(当前点的父节点),要么与支配集中的点相连(当前节点和当前节点的父节点的父节点).

具体实现:

　　采用链式前向星存储整棵树.整形数组newpos[i] 表示深度优先遍历序列的第 i 个点是哪个点, now 表示当前深度优先遍历序列已经有多少个点了. bool形数组visit[]用于深度优先遍历的判重,整形pre[i]表示点 i 的父节点编号, bool型数组s[i]如果为 true, 表示第 i 个点被覆盖, bool型数组set[i]如果为 true,表示点 i 属于要求的点的集合.

代码

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1000;
int pre[maxn];//存储父节点
bool visit[maxn];//DFS标记数组
int newpos[maxn];//遍历序列
int now;
int n, m;

int head[maxn];//链式前向星
struct Node {int to; int next;};
Node edge[maxn];

void DFS(int x) {
    newpos[now ++] = x;//记录遍历序列
    for(int k = head[x]; k != -1; k = edge[k].next) {
        if(!visit[ edge[k].to ]) {
            visit[ edge[k].to ] = true;
            pre[edge[k].to] = x;//记录父节点
            DFS(edge[k].to);
        }
    }
}

int MDS() {
    bool s[maxn] = {0};
    bool set[maxn] = {0};
    int ans = 0;
    for(int i = n - 1; i >= 0; i--) {//逆序进行贪心
        int t = newpos[i];
        if(!s[t]) { //如果当前点没被覆盖
            if(! set[ pre[t] ]) {//当前点的父节点不属于支配集
                set[ pre[t] ] = true;//当前点的父节点加入支配集
                ans ++;  //支配集节点个数加 1
            }
            s[t] = true; //标记当前点已被覆盖
            s[ pre[t] ] = true;// 标记当前点的父节点被覆盖
            s[ pre[ pre[t] ] ] = true;//标记当前点的父节点的父节点被覆盖
        }
    }
    return ans;
}

int main() {
    /* read Graph message*/ //建图
    memset(visit, false, sizeof(visit));//初始化
    now = 0;
    visit[1] = true;
    pre[1] = 1;
    DFS(1);//从根节点开始寻摘遍历序列
    MDS();
    return 0;
}