树的重心-java

重要通过深度优先搜索来完成树的重心，其中关于树的重心的定义可以结合文字多加明白。
  文章目录
   前言☀
  一、树的重心☀
  二、算法思路☀
  1.图用毗邻表存储
  2.图的遍历
  3.算法思路 
  二、代码如下☀
  1.代码如下：
  2.读入数据
  3,代码运行结果
  总结
  

---

前言☀

重要通过深度优先搜索来完成树的重心，其中关于树的重心的定义可以结合文字多加明白。

---

提示：以下是本篇文章正文内容，下面案例可供参考
一、树的重心☀

给定一颗树，树中包罗 n 个结点（编号 1∼n）和 n−1 条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中结点数的最大值最小，那么这个节点被称为树的重心。
输入格式
第一行包罗整数 n，表示树的结点数。
接下来 n−1行，每行包罗两个整数 a 和 b，表示点 a 和点 b 之间存在一条边。
输特殊式
输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。
数据范围
1≤n≤100000
二、算法思路☀

1.图用毗邻表存储

我们通过一个链表数组来存储，我们把数组中每一个链表的出发点对应图中的一个结点，然后与该结点相连的结点，挂在数组中对应起始结点的后面即可，图示如下：

图1.1图毗邻表存储 

我们引入一维整型数组e，存储链表里面的各个结点的值；一维整型数组ne里面存储结点的下一个结点在数组e里面的索引值；整型变量index表示新创建结点在e数组中的下标。
一位整型数组head用来存储图中的每个节点，head表示以i结点为出发点的单链表的头结点，链表中的每一个结点都是与i相连的结点，如图1.1所示。故head数组里面的值初始化为-1，表示此时链表都为空。
我们新创建的结点值为b即e[index] = b；然后将新创建的结点头插法插入，即将原本头结点后的所有结点链接到新结点后面即ne[index] = head[a]；然后再将头结点指向新创建的结点head[a] = index。注意让index++，包管index一直指向新创建的结点。

1.     //添加边
2.     //头插法
3.     public static void add(int a,int b){
4.         e[index] = b;
5.         ne[index] = head[a];
6.         head[a] = index++;
7.     }

复制代码

关于单链表的基本操作还有不明白的可以去看我的单链表-java-CSDN博客 这篇博客，里面有对单链表操作的各种具体介绍。

2.图的遍历

无向图是特殊的有向图，树也是特殊的图，故我们只必要思量有向图即可。 

 

图2.1深度优先遍历示例图 

深度优先遍历着实就是一条路走到止境，每当我们走过一个结点会设置一个标记表示已经走过了。当我们走到止境无法再走时就回退到上一个结点，然后从该结点看看有无别的没走过的路径，无路可走时再回退到上一个结点，所有结点都被走过后就完成了深度优先遍历。依次走过的结点次序如图2.1的黄色数字形貌的次序一致。
 

图2.2广度优先遍历示例图

 广度优先遍历也叫层序遍历，我们一层一层逐层遍历。可以通过队列模仿，将根结点入队；当队列不为空，弹出结点，然后再将与该结点相连的结点一次入队，重复上述操作，直到队列为空，就遍历的所有的结点。
遍历的次序如图2.2模仿所示，黄色数字表示层数。
3.算法思路 

 图3.1样例模仿

图3.2删除结点1连通块情况 

图3.3删除结点2连通块情况 

图3.4删除结点4各个连通块情况 

树的重心：删除一个结点后，剩下的连通块中结点个数最多但是在删除各个结点的连通块中的结点数最小的，那么这个结点就是树的重心。通过上述图3.1-3.4的示例，即我们删除1结点连通块中结点最多是4，删除结点2连通块中结点最多是6，删除结点4连通块中结点最多是5，等等，我们可以知道结点1就是树的重心。

图3.5示例图 

 我们用深度优先搜索dfs来确定根节点u的结点的个数；当前结点遍历过设置为flag = true；然后用整型变量sum来统计结点的个数，初始化为1（根节点自己），然后访问与u相连的边，如果没有被访问过，就接着对该边进行dfs深度优先搜索，然后更新为删除这一节点后所剩的连通图的结点数量的最大值；将sum加上子树的结点个数就是以u为根节点的结点的个数。
比力删除u后的u子树中最大的连通块(6,3-9中的更大者),和整个树减u子树剩下的连通块(1-2-8-5-7)
 res = Math.max(n - sum,res)。
sum：表示以这一点为根结点的树中所有结点个数
res：表示删除这一点后的连通块中结点数量的最大值(不断更新)
ans：表示所有(依次删除每个结点的情况)最大连通结点数量的最小值,即各个res的最小值(不断更新)
所有备注可结合上方图示一起看

1.     //深度优先搜索
2.     //以u为根节点的结点的个数
3.     public static int dfs(int u){
4.         //当前点被搜过了
5.         flag[u] = true;
6.         //存储以u为结点
7.         int sum = 1;
8.         //存储当前删掉某个结点后最大连通子图的个数
9.         int res = 0;
10.         //访问u的子节点
11.         for(int i = head[u];i != -1;i = ne[i]){
12.             int j = e[i];
13.             if(!flag[j]){
14.                 int s = dfs(j);
15.                 res = Math.max(s,res);
16.                 //以u为根结点的树结点数量=1+它各个子树的结点数量
17.                 sum += s;
18.             }
19.         }
20.         // 比较删除u后的u子树中最大的连通块(6,3-9中的更大者),和整个树减u子树剩下的连通块(1-2-8-5-7)
21.         res = Math.max(n - sum,res);
22.         //所有最大的连通块结点数目找到最小值
23.         ans = Math.min(ans,res);
24.         return sum;
25.     }

复制代码

二、代码如下☀

1.代码如下：

2. import java.io.*;
3. import java.util.Arrays;
4. import java.util.Scanner;
6. public class 树的重心 {
7.     static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
8.     static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
9.     static int N = 100010,M = N * 2;
10.     //记录头结点
11.     static int[] head = new int[N];
12.     //存储结点的值
13.     static int[] e = new int[M];
14.     //存储当前结点的下一个结点的索引值
15.     static int[] ne = new int[M];
16.     //最新创建的结点的索引即数组e中空最新的空结点的索引
17.     static int index;
18.     //用来存储结点是否被遍历过了
19.     static boolean[] flag = new boolean[N];
20.     static int n;
22.     static int ans = N;
23.     public static void main(String[] args) {
24.         Scanner sc = new Scanner(br);
25.         n = sc.nextInt();
26.         Arrays.fill(head,-1);
27.         for (int i = 0;i < n - 1;i++){
28.             int a = sc.nextInt();
29.             int b = sc.nextInt();
30.             add(a,b);
31.             add(b,a);
32.         }
33.         dfs(1);
34.         pw.print(ans);
35.         pw.flush();
36.     }
37.     //深度优先搜索
38.     //以u为根节点的结点的个数
39.     public static int dfs(int u){
40.         //当前点被搜过了
41.         flag[u] = true;
42.         //存储以u为结点
43.         int sum = 1;
44.         //存储当前删掉某个结点后最大连通子图的个数
45.         int res = 0;
46.         //访问u的子节点
47.         for(int i = head[u];i != -1;i = ne[i]){
48.             int j = e[i];
49.             if(!flag[j]){
50.                 int s = dfs(j);
51.                 res = Math.max(s,res);
52.                 //以u为根结点的树结点数量=1+它各个子树的结点数量
53.                 sum += s;
54.             }
55.         }
56.         res = Math.max(n - sum,res);
57.         //所有最大的连通块结点数目找到最小值
58.         ans = Math.min(ans,res);
59.         return sum;
60.     }
61.     //添加边
62.     public static void add(int a,int b){
63.         e[index] = b;
64.         ne[index] = head[a];
65.         head[a] = index++;
66.     }
67. }

复制代码

2.读入数据

1. 9
2. 1 2
3. 1 7
4. 1 4
5. 2 8
6. 2 5
7. 4 3
8. 3 9
9. 4 6

复制代码

3,代码运行结果

1. 4

复制代码

---

总结

这次多看一下图示，明白各变量的意义，代码是简介，其中的意思要多加明白。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。