第三章搜索与图论

目录
1 树和图的存储1.1 邻接矩阵1.2 邻接表
2 树和图的遍历2.1 深度优先遍历2.2 宽度优先遍历

1 树和图的存储
树是一种特殊的图，其存储方式与图的存储方式相同； 对于无向图而言，可以按照有向图来存储，即对无向图的边a - b，存储两条有向图的边即可a -> b; b -> a；
因此仅考虑有向图的存储即可。
有两种存储方式：
1.1 邻接矩阵
适用于存储边稠密的图。
1.2 邻接表
适用于存储边稀疏的图。
int h[N], e[N], idx; // 与单链表一样

// 添加一条有向边 a -> b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

2 树和图的遍历

第三章搜索与图论最先出现在Python成神之路。