树与图

树是一种特殊的图：无环连通图。

图也分为两种：

• 有向图：边是有方向的（点之间可以连线）
• 无向图：边是没有方向的（可以看作是有两条有向边），无向图是一种特殊的有向图

因此我们只需要研究 有向图 如何存储即可。

有向图

有向图的存储分为两类：

• 邻接矩阵：二维数组 g[a][b]
  • 存储 a -> b 这一条边的信息（权重或者 bool 值）
  • 无法存储重边
  • 空间复杂度较高 $O(n^2)$，比较适合稠密图（边很多的情况）
• 邻接表：$n$ 个单链表，$n$ 为节点个数
  • 单链表上的节点为该节点能走到的点
  • 采用 头插法 插入
  • 似乎没有存储边的权重

邻接表存储：

const int N = 1e5 + 10, M = N * 2;
int h[N], e[M], ne[M], idx;

void init() {
    memset(h, -1, sizeof h);
}

// add one edge: node k -> node t
void add(int k, int t) {
    e[idx] = t;
    ne[idx] = h[k];
    h[k] = idx;
    idx ++;
}

• idx 这里可以理解为边的编号（而不是前面的节点编号）
• e[idx] 表示该有向边连到什么 点
• ne[idx] 表示该有向边连到什么 边

有向图的深度优先遍历：

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);
        }
    }
}

• 从编号为 u 的点出发
• 首先将 u 置为 已搜索 状态
• 对于所有 u 邻接表中能到达的点进行搜索，找到 j = e[i] 对应编号
• 如果编号为 j 的点尚未搜索过，深入一层，继续搜索

有向图的宽度优先遍历：

树的重心

找连通块的 点的个数 最小的最大值。

递归树的每个点，可以算出删除这个点后剩下的 各个连通块 的点个数的值。

递归返回值就是该节点为根节点的子树中节点的个数

图中点的层次

所有边的长度为 1，同时求最短距离。

先把距离全部初始化为 -1，然后判断如果距离是 -1 就说明没有遍历过。