树和图的基本概念

树

有向无环连通图

图

分类

有向图 a->b 无向图 a->b, b->a 连通图，非连通图

顶点，入度，出度

环，自环

边，重边

图的存储

• 邻接矩阵 ：用的比较少，原因：比较浪费空间；比较适合稠密图
• 邻接表 ：用的最多，其实就是单链表，拉链法的 hash 表

图的邻接表表示

个人为了弄懂 邻接表表示的模板代码，做了以下工作：

一、首先 弄清楚 几个数组的含义，然后再去 看 邻接表的表示代码，发现容易理解一些，在这里再次回顾下几个数组的含义：

$h[N]$ : 表示 第 i 个节点的 第一条边的 idx $ne[M]$ : 表示 与 第 idx 条边 同起点 的 下一条边 的 idx $e[M]$ : 表示 第 idx 条边的 终点

$N$ ： 节点数量 $M$：边的数量 $i$ : 节点的下标索引 $idx$ ： 边的下标索引 二、然后结合代码模版理解定义

变量初始化定义：

int h[N], e[M], ne[M], idx;
// e[M] : ver数组，顶点数组，存储每条边的顶点（终点）
// h[N]: head数组，存储的是 ver数组的下标
// ne[M]: next数组

初始化图

memset(h, -1, sizeof h);

当我们加入一条边的时候：

public static void add(int a,int b){
    e[idx] = b;      // 记录 加入的边 的终点节点b
    ne[idx] = h[a]; // h[a] 表示 节点 a 为起点的第一条边的下标，ne[idx] = h[a] 表示把 h[a] 这条边接在了 idx 这条边的后面，其实也就是把 a 节点的整条链表 接在了 idx 这条边 后面；目的就是为了下一步 把 idx 这条边 当成 a 节点的单链表的 开头的第一条边，完成把最新的一条边插入到 链表头的操作；
    h[a] = idx++; // a节点开头的第一条边置为当前边，idx移动到下一条边
}

三、我去继续写题，理解深入了再回来补充邻接表表示的妙处所在；这里作为给初学者的一些提示

枚举以 节点 $i$ 为起点 的所有 出边

for (int idx = h[i]; idx != -1; idx = ne[idx]){ // 枚举所有的 以i节点开头的单链表 元素
    printf("%d -> %d\n", i, e[idx])
}