Java教程

树的重心

本文主要是介绍树的重心,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

树的重心

定义:
重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。
不妨设max_part(x)为在删除节点x后产生的子树中,最大的一颗大小。那么树的重心就是使得max_part函数取到最小的节点p就是整颗树的重心。

void dfs(int x)
{
    v[x] = 1; size[x] = 1; //设置子树的大小;
    int max_part = 0; //表示删除x后最大子树的大小;
    
    for (int i = head[x]; i; i = ne[i]) 
    {
        int y= ver[i];
        if (v[y]) continue;  //点y已经被访问过了;
        dfs(y);
        size[x] += size[y]; //从子节点更新到父节点
        max_part = max(max_part, size[y]);
    }
    max_part = max(max_part, n - size[x]);
    if (max_part < ans ) {
        ans = max_part; //全局量记录重心对应的max_part
        pos = x;  //全局量pos记录重心;
    }
}

图里联通块计数

本质上还是图着色,这里用cnt表示不同的颜色。

void dfs(int x)
{
    v[x] = cnt;
    for (int i = head[x]; i; i = ne[i]) {
        int y = ver[i];
        if (v[y]) continue;
        dfs(y);
    }
}

//依次着色森林;
for (int i = 1; i <= n; i++) {
    if (!v[i]) {
        cnt++;
        dfs(i);
    }
}

参考

  1. 算法进阶指南
  2. ACwing
这篇关于树的重心的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!