树和图的存储与遍历
树和图的存储
树是一种无环连通图，是一种特殊的图
图分为有向图和无向图
图的两种常用存储方式：
- 邻接矩阵
g[a][b]： 用 n×n 的二维数组记录边（有边存边权，无边存 INF）。优点是查询”任意两点之间是否有边、边权多少”是 O(1)；缺点是空间 O(n²)，只适合点数较少（一般 n ≤ 1000）的稠密图。 - 邻接表（数组模拟）： 每个点维护一条单链表，链上挂着从它出发能直接到达的所有邻居。空间 O(n + m)，适合稀疏图，也是竞赛中最常用的存图方式。
数组模拟邻接表的模板： h[a] 存”从 a 出发的第一条边的编号”，e[idx] 存这条边指向的点，ne[idx] 存下一条边的编号，w[idx] 可以存边权，idx 是全局的”边分配器”。
int[] h = new int[N], e = new int[M], ne = new int[M]; // 无向图时 M 取边数的 2 倍int idx = 0;
void add(int a, int b) { // 添加一条 a -> b 的边（头插法） e[idx] = b; ne[idx] = h[a]; h[a] = idx++;}要点： h 数组要初始化为 -1（表示链表末尾）；无向图要 add 两次（a→b 和 b→a），所以边数组开 2 倍大小；遍历”从 u 出发的所有边”用 for (int i = h[u]; i != -1; i = ne[i])，其中 e[i] 就是邻居编号。
树和图的遍历
图的遍历有两种基本方式：
- DFS（深度优先搜索）： 沿一条路走到底、撞墙再回溯，用递归实现。树上的 DFS 常用于”自底向上”统计信息，例如求每棵子树的大小——先递归完所有儿子，再把儿子的结果汇总到父亲。
- BFS（广度优先搜索）： 一层一层向外扩展，用队列实现。当每条边长度都为 1 时，BFS 第一次到达某个点的距离就是最短距离，因此常用于求无权图的最短路。
遍历时务必用标记数组（如 mark[] 或距离数组 d[]）防止重复访问——树虽然没有环，但无向边会”走回头路”，不标记就会在两个点之间来回打转、无限递归。
树的重心（dfs）
树的重心-dfs
给定一棵树，树中包含 n 个结点（编号 1~n）和 n-1 条无向边。 请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式
第一行包含整数 n，表示树的结点数。 接下来 n-1 行，每行包含两个整数 a 和 b，表示点 a 和点 b之间存在一条边。
输出格式
输出一个整数 m，表示重心的所有子树中最大的子树的结点数。
数据范围
1 ≤ n ≤ 10⁵
import java.util.*;import java.io.*;public class Main { static int idx = 0; static int N = 100010; static int n; static int M = 2 * N;//因为是无向图所以存储的时候无向边可以当做双向边来存储 static int[] e = new int[M], h = new int[N], ne = new int[M];//使用邻接表存储树或者图 static boolean[] mark = 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++; }
//以u为根的子树的节点数 public static int dfs(int u) { mark[u] = true; int sum = 1, res = 0; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!mark[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().trim()); Arrays.fill(h, -1);//初始化邻接表 for (int i = 0; i < n - 1; i++) { String[] nm = br.readLine().trim().split("\\s+"); int n = Integer.parseInt(nm[0]), m = Integer.parseInt(nm[1]); //因为是无向图所以添加双向边 add(n, m); add(m, n); } dfs(1); System.out.print(ans);
}}图中点的层次（bfs）
图中点的层次-dfs
给定一个 n 个点 m 条边的有向图，图中 可能存在重边和自环。 所有边的长度都是 1，点的编号为 1 ~ n。 请你求出 1 号点到 n 号点的最短距离，如果从 1 号点 无法走到 n 号点，输出 -1。
输入格式
第一行包含两个整数 n 和 m。 接下来 m 行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1 的边。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
数据范围
1 ≤ n, m ≤ 10⁵
import java.util.*;import java.io.*;public class Main{ static int N = 100010; static int[] e = new int[N],ne = new int[N],h = new int[N],d = new int[N]; static int idx = 0;
static void add(int a,int b){ e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } public static void bfs(){ LinkedList<Integer> aq = new LinkedList<>();//创建一条双向链表（Java 标准库），用来当队列、栈、双端队列都行 Arrays.fill(d,-1);//初始化距离数组 d[1] = 0; aq.offer(1); while(!aq.isEmpty()){ int top = aq.peek(); for(int i = h[top];i != -1;i = ne[i]){ int j = e[i]; if(d[j] == -1){ d[j] = d[top] +1; aq.offer(j); } } aq.poll(); }
} public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] nm = br.readLine().trim().split("\\s+"); int n = Integer.parseInt(nm[0]); int m = Integer.parseInt(nm[1]); Arrays.fill(h,-1); for(int i = 0;i < m;i++){ String[] ab = br.readLine().trim().split("\\s+"); int a = Integer.parseInt(ab[0]); int b = Integer.parseInt(ab[1]); add(a,b); } bfs(); System.out.println(d[n]); }}拓扑序列
拓扑排序针对有向无环图（DAG）：把图中所有点排成一个序列，使得对每条有向边 (x, y)，x 都排在 y 的前面。
核心是”入度”： 一个点的入度 = 指向它的边的数量。入度为 0 的点没有任何前置依赖，可以排在序列最前面。Kahn 算法（BFS 版）步骤：
- 统计每个点的入度 d；
- 把所有入度为 0 的点入队；
- 每次取出队头 t 并输出，同时”删掉”t 的所有出边——把 t 的每个邻居 j 的入度减 1，若减到 0 就入队；
- 若最终输出的点数等于 n，说明所有点都成功排入序列，图无环；否则说明图中存在环，拓扑序列不存在，输出 -1。
为什么有环就一定没有拓扑序列？ 环上的点互相依赖（a 依赖 b、b 依赖 a……），环中每个点的入度永远 ≥ 1，谁也进不了队。反之，无环图每一步总能找到入度为 0 的点，所以 DAG 一定有拓扑序列（且通常不唯一）。
有向图的拓扑序列
给定一个 n 个点 m 条边的有向图，图中 可能存在重边和自环。 请输出 任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出
-1。定义
若一个由图中所有点构成的序列 A 满足： 对于图中的每条边 (x, y)，x 在 A 中都出现在 y 之前， 则称 A 是该图的一个拓扑序列。
输入格式
第一行包含两个整数 n 和 m。 接下来 m 行，每行包含两个整数 x 和 y，表示点 x 和点 y 之间存在一条有向边 (x, y)。
输出格式
共一行，如果存在拓扑序列，则输出拓扑序列（任意一个即可）。 否则输出
-1。数据范围
1 ≤ n, m ≤ 10⁵
import java.util.*;import java.io.*;
public class Main { static int N = 100010; static int[] h = new int[N], e = new int[N], ne = new int[N], d = new int[N], q = new int[N]; static int idx;
static void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; d[b]++; // b 的入度 +1 }
// Kahn 算法：入度为 0 的点入队，依次出队并删除其出边 static boolean topSort(int n) { int hh = 0, tt = -1; for (int i = 1; i <= n; i++) if (d[i] == 0) q[++tt] = i; while (hh <= tt) { int t = q[hh++]; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (--d[j] == 0) q[++tt] = j; } } return tt == n - 1; // 所有点都入过队 ⇔ 无环 ⇔ 存在拓扑序列 }
public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] nm = br.readLine().trim().split("\\s+"); int n = Integer.parseInt(nm[0]); int m = Integer.parseInt(nm[1]); Arrays.fill(h, -1); while (m-- > 0) { String[] ab = br.readLine().trim().split("\\s+"); add(Integer.parseInt(ab[0]), Integer.parseInt(ab[1])); } if (topSort(n)) { for (int i = 0; i < n; i++) System.out.print(q[i] + " "); } else { System.out.println(-1); } }}如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时