寒假学习算法

短命女 2024-03-27 15:11 61阅读 0赞

## 树与图的深度优先遍历 ##

#### 邻接表 ####

邻接表（Adjacency List）顾名思义，就是通过**链表**或者利用**数组模拟链表**的方式将图的相连接关系表示的一种方法，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。 如这个表头结点**所对应的顶点**存在**相邻顶点**，则把**相邻顶点**依次存放于表头结点所指向的**单向链表**中。

## 分析 ##

**重心**定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。  
树的重心：运用**DFS**\+**邻接表**  
**DFS**:递归处理根节点的子树的节点个数  
**邻接表**：找到节点的邻接点，继续递归，走到叶子节点时，再往上返回，直至回到根节点，再以当前根节点的邻接点作为根节点，再`DFS`,确保每一个点都会走到。

### 问题分析： ###

根据重心的定义：  
**(1)如果将这个点删除后，剩余各个连通块中点数的最大值。**  
我们需要遍历各个根节点，将根节点的最大子树保存下来。  
**(2)剩余各个连通块中点数的最大值最小。**  
再将各个根节点的最大子树进行比较，得出最小值，**即是重心，即为答案。**

## 模拟 ##

以`u=1`作为根节点，一条路走到黑，走到叶子节点，最后返回到根节点`1`。  
![7a9b693ab58e449fb0b35f8c859187ba.jpeg_pic_center][]  
由于从`1`开始，无法体现下面与上面部分的比较  
走完`u=1`，接下来走到`u=2`，以`u=2`为根节点。  
![在这里插入图片描述][3ddae6fe2a0d46e3a19605f5ef62285a.jpeg_pic_center]

**注：可以看到从根节点出发，递归其根节点的邻接节点，邻接节点继续递归他的邻接节点，他的邻接节点继续递归他的邻接节点，直至往下走到叶子节点，即往下再无路可走时，往上返回，直至回到根节点。  
在这过程中，记录根节点的邻接节点的最大子树。再将一路走过的点进行求和，便于求解根节点的上面连通块部分。再以根节点的邻接点为根节点出发，继续往下dfs，如此循环往复，走便所有的点为止。**

## 代码 ##

import java.util.*;
    public class Main{
        static int N=100010,M=N*2,idx,n;//输入的数是点数的两倍
        static int h[]=new int[N];
        
        static int e[]=new int[M];//最多有2倍
        static int ne[]=new int[M];//最多有2倍
        static boolean st[]=new boolean[N];//标记哪个点已走过
        static int ans=N;//先定义一个比较大的数，用于比较最小值。
        public static void add(int a,int b){//单链表存边
            e[idx]=b;//存值
            ne[idx]=h[a];
            h[a]=idx;//存边，h[a]表示的是边的编号，也是对应插入点的编号。
            idx++;
        }
        public static int dfs(int u){
            int sum=1;//本身算作一个点，用于求某个连通块的节点总数
            int res=0;//结果
            st[u]=true;//表示该节点走过，保证往下搜，防止再向上查找一遍，造成死循环。
            for(int i=h[u];i!=-1;i=ne[i]){//遍历邻接表的边
            int j = e[i];//找到节点的邻接节点。
            if(!st[j]){//如果没有走过，就dfs该节点，继续递归下去，直至走到叶子节点。
                int s = dfs(j);//让该邻接节点作为根节点，dfs该节点，统计他子树的子节点个数。
                res=Math.max(res,s);//保留的是该节点的最大子树
                sum+=s;//将该节点的各子树的节点数都加起来，便于求上面连通块的节点数。
            }
            }
            res=Math.max(res,n-sum);//比较上面连通块和下面连通块的节点数，看哪个部分比较大
            ans=Math.min(res,ans);//保存各根节点的最大子树的最小值，即删除重心，也就是答案
            return sum;//返回sum，递归处理走到的点。
        }
        public static void main(String []args){
            Scanner in = new Scanner(System.in);
             n = in.nextInt();                          
            for(int i=1;i<N;i++){
                h[i]=-1;初始化，链表开始是均指向-1
            }
            for(int i=0;i<n-1;i++){
            int a= in.nextInt();
            int b =in.nextInt();
            //无向边
            add(a,b);//a-->b
            add(b,a);//b-->a
            }
            dfs(1);
            //从1开始dfs，理论上任意一个点都可以，保险起见，防止输入的点只有一个1的情况
            System.out.println(ans);
    }
    }

[7a9b693ab58e449fb0b35f8c859187ba.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/de668292746345f6b76372d2a4ca886e.png
[3ddae6fe2a0d46e3a19605f5ef62285a.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/9811f15f2beb44c6899b43d1a49bca2b.png