树的存储和遍历

树的存储和遍历方法

首先：树是一种特殊的图，无环连通图

存储树，就是存储图，

图分为

• 有向图
• 无向图，无向图是特殊的有向图，

树的存储

存储的方式：

• 领接矩阵
• 领接表

代码实现

// 领接表存储
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N],e[N],ne[N],idx;

//添加一条边  a-b
void add(int a, int b){
    e[idx] = b,ne[idx]=h[a],h[a]=idx++;
}

//初始化
idx = 0;
所有的h[N] = -1;

树的遍历

dfs和bfs

代码实现

//DFS
int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}



//BFS
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

//手写队列版本BFS
private static int bfs() {
        //bfs 队列
        int hh = 0, tt=0;
        q[0] = 1;   
        
        Arrays.fill(d, -1);
        
        //d是从1开始
        d[1]=0; //0表示遍历过了
        while(hh<=tt){
            int t = q[hh++]; //出队
            for(int i=h[t];i!=-1;i=ne[i]){
                int j = e[i];
                if(d[j]==-1){
                    d[j] = d[t]+1;
                    q[++tt]=j; //入队
                }
                        
            }
        }
    return d[n];    
}

题目

Acwing

• 846 树的重心 DFS
• 847 图中点的层次 BFS

解答

AC846 树的重心

关键：重心的概念要好好理解

package Chapter3;
/**
 * 
 * 
 * ACwing 846  数的重心
 * 树的存储和遍历
 * @author vccyb
 *
 */


import java.io.*;
import java.util.Arrays;

public class P846 {
    private static final int N = 100010, M = N * 2;
    //存储树的领接表
    private static int[] h = new int[N], e = new int[M], ne = new int[M];
    //st表示这个表是否搜过，dfs
    private static boolean[] st = new boolean[N];
    private static int ans = N, idx, n;
    
    
    private static void add(int a, int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    
    
    private static int dfs(int u){
        st[u] = true;
        int sum = 1;
        int res = 0;
        for(int i=h[u];i!=-1;i=ne[i]){
            int j = e[i];
            if(!st[j]){
                //这里是返回j点的子节点总数
                int s = dfs(j);
                res = Math.max(res, s);
                sum += s; //连通块的子节点数量加上
            }
            
        }
        
        res = Math.max(res, n-sum);
        
        ans = Math.min(res, ans);
        return sum;
    }
    
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        Arrays.fill(h, -1);
        for(int i=0;i<n-1;i++){
            String[] str = br.readLine().split(" ");
            int a = Integer.parseInt(str[0]);
            int b = Integer.parseInt(str[1]);
            add(a,b);
            add(b,a);
        }
        
        dfs(1);
        System.out.println(ans);
        
        
        
    }
    
}

Acwing847 图种点的层次

package Chapter3;

/**
 * 
 * Acwing 图种点的层次
 * BFS
 * @author vccyb
 *
 */

import java.io.*;
import java.util.*;
public class P847 {
    private static final int N = 100010;
    private static int idx,n,m;
    private static int[] h = new int[N];
    private static int[] e = new int[N];    
    private static int[] ne = new int[N];
    //d和q
    //d是深度，q是队列
    private static int[] d = new int[N];
    private static int[] q = new int[N];
    
    
    private static void add(int a, int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    
    private static int bfs() {
        //bfs 队列
        int hh = 0, tt=0;
        q[0] = 1;   
        
        Arrays.fill(d, -1);
        
        //d是从1开始
        d[1]=0; //0表示遍历过了
        while(hh<=tt){
            int t = q[hh++]; //出队
            for(int i=h[t];i!=-1;i=ne[i]){
                int j = e[i];
                if(d[j]==-1){
                    d[j] = d[t]+1;
                    q[++tt]=j; //入队
                }
                        
            }
        }
        
        return d[n];
        
        
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);
        
        //初始化h
        Arrays.fill(h, -1);
        
        for(int i=0;i<m;i++){
            String[] line2 = br.readLine().split(" ");
            int a = Integer.parseInt(line2[0]);
            int b = Integer.parseInt(line2[1]);
            add(a,b);  //注意是有向图
        }
        
        int ans = bfs();
        System.out.println(ans);
        br.close();
    }
    
}