树

树是无环连通图

树是无向图，因此边插入需要插入两次

树是无向图，因此可以对任意一节点dfs()作为根节点

深度优先搜索

初始化时，注意给出的节点值，范围可能为[1, n]

注意使用st[N]，避免搜索到父节点

用无向图存储，注意无法区分其相邻节点为子节点还是父节点
通过使用深度优先搜索，来区分对于当前访问节点的父节点（以及访问过的节点）和子节点（未访问过的节点）Acwing 3990 统计每棵子树的大小

可以使用hasFather[]来标记是否含有父节点，从而判断出根节点 Acwing 285

图

1. 有向图：图的边具有方向性
2. 无向图：图的边不具有方向性，但可以通过建立两条有向边来实现，因此是一种特殊的有向图

有向图的存储

1. 邻接矩阵,g[a, b] a->b,空间复杂度为$O(n^2)$
2. 邻接表,每个点都维护一个单链表，存储相邻出边的点

h[N]存储链表的头节点的下标
e[M]存储链表的元素值
ne[M]存储元素的next
idx为哨兵

初始化

void init() {
    for (int i = 0; i < N; i++) h[i] = -1; // 初始链表指向空节点
}

插入边a->b

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    idx++;
}

无向图的存储

使用有向图的存储，两次两条反向边，边数最多为$2 M$

注意有向图插入只需调用一次add(a, b)
而无向图需调用两次add(a, b) add(b, a)

图的遍历

深度优先搜索

boolean st[N] 维护节点是否被遍历过

void dfs(int u) {
    st[u] = true; // 标记已经被搜索

    for (int i = h[u]; i != -1; i = ne[i]) { // 搜索所有出边
        int j = e[i]; // 注意取出节点
        if (!st[j]) dfs(j); // 没有搜索过，则向下搜索
    }
}

注意可以根据题目返回值

宽度优先搜索

d[N]维护1到其他节点的距离，Deque<Integer> q维护双端队列或使用模拟队列

void bfs(int n) {
    for (int i = 0; i <= n; i++) d[i] = -1;
    q[++tt] = 1;
    d[1] = 0;
    while (hh <= tt){
        int k = q[hh++];
        for (int j = h[k]; j != -1; j = ne[j]) {
            int p = e[j];
            if (d[p] == -1) {
                d[p] = d[k] + 1;
                q[++tt] = p;
            }
        }
    }
}

拓扑序列

有向无环图才存在拓扑序列，也被称为拓扑图

若存在环，由于不存在入度为0的点，因此不存在拓扑序列

由于得到拓扑序列，每次会取出入度为0的点，然后影响相邻点的入度，因此可以采用类似宽度优先搜索的方法

d[N]维护了所有节点的入度，在插入边a -> b时d[b]++

void bfs() {
    for (int i = 1; i <= n; i ++) {
        if (d[i] == 0) q[++tt] = i; // 将所有入度为0的点入队
    }
    while(hh <= tt) { 
        int t = q[hh++];
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            d[j] --; // 删除相邻边等价于减少相邻点的度数
            if (d[j] == 0) q[++tt] = j; // 将新的度数为0的点加入到队列中
        }
    }
}

注意若存在拓扑序列，则该队列必定存储过n个节点，因此最终hh = n, tt = n - 1，且由于队列维护了元素的先后顺序，因此队列中元素恰好为拓扑序列

if (hh == n) for (int i = 0; i < n; i++) wr.write(q[i] + "");

否则，说明图中存在环，入度无法为0，无法加入到队列中

链表形式邻接表

声明及其初始化

ArrayList<Integer>[] edges = new ArrayList[N];
for (int i = 0; i < N; i++)    
    edges[i] = new ArrayList<>();

插入a -> b

void add(a, b) {
    edges[a].add(b);
}

DFS
boolean[] flag = new boolean[N];标记是否访问过

public int dfs(int i) {
    flag[i] = true; 
    for (int j : edges[i]) {
        if (!flag[j]) { // 避免访问相邻节点市重新访问已访问过的节点(父节点)，导致无限递归

        }
    }
}