本文共 2626 字，大约阅读时间需要 8 分钟。

树与图的深搜与广搜模板

一.图的存储

二.模板

深搜:

import java.util.*;public class Main{
       static int[] head = new int[100010];    static int[] nodes = new int[200010];    static int[] next = new int[200010];    static boolean[] vis = new boolean[100010];    static int n;    static int index = 1;    static int last;    static int dfs(int start){
           vis[start] = true;        int sum = 1;        int res = 0;        for(int i=head[start];i!=-1;i=next[i]){
               int j = nodes[i];            if(!vis[j]){
                   int kk = dfs(j);                res = Math.max(kk,res);                sum += kk;            }        }        res = Math.max(res,n-sum);        last = Math.min(res,last);        return sum;    }    static void add(int a,int b){
           nodes[index] = b;        next[index] = head[a];        head[a] = index++;    }    public static void main(String[] args){
           Scanner scan = new Scanner(System.in);        n = scan.nextInt();        int a,b;        last = n;        for(int i=1;i<=n;i++) head[i] = -1;        for(int i=1;i<=n-1;i++){
               a = scan.nextInt();            b = scan.nextInt();            add(a,b);            add(b,a);        }        dfs(1);        System.out.print(last);    }}

广搜:

import java.util.*;public class Main{
       static int[] h = new int[100010];    static int[] nodes = new int[100010];    static int[] next = new int[100010];    static boolean[] vis = new boolean[100010];    static int[] dist = new int[100010];    static int[] q = new int[100010];    static int index = 1;    static void add(int a,int b){
           nodes[index] = b;        next[index] = h[a];        h[a] = index++;    }    public static void main(String[] agrs){
           Scanner scan = new Scanner(System.in);        int n,m;        n = scan.nextInt();        m = scan.nextInt();        int a,b;        for(int i=1;i<=n;i++){
               h[i] = -1;        }        for(int i=1;i<=m;i++){
               a = scan.nextInt();            b = scan.nextInt();            add(a,b);        }        int head = 0;        int tail = 0;        q[head] = 1;        dist[1] = 0;        vis[1] = true;        while(head<=tail){
               int t = q[head++];            for(int i = h[t];i!=-1;i=next[i]){
                   int ss = nodes[i];                if(!vis[ss]){
                           dist[ss] = dist[t]+1;                        q[++tail] = ss;                        vis[ss] = true;                }            }        }        if(dist[n]==0){
               System.out.print(-1);        }else{
               System.out.print(dist[n]);        }    }}

转载地址：http://holzi.baihongyu.com/