树和图的存储和遍历

一般来说有两种存储方式
树是特殊的图（无环连通图）
分为两种
有向图    无向图
a->b        a->b,b->a
所以只考虑有向图
记录方式：
1、邻接矩阵 g[a,b]（只能存同向的一条边，空间复杂度O(n^2)适合稠密图）
2、邻接表（单链表）
        给每个点开一个单链表，单链表存能到达的点。当插入新边时可以插在每个链表头部。
遍历：
两种方式： DFS    BFS
只考虑有向图的遍历
acwing 848题
DFS函数遍历之后返回以传入参数为根子树点的数量。
acwing 847题
使用宽搜来求最短路。
图的宽搜经典应用 ： 求拓扑序列（只有有向图）  （acwing 848）
入度和出度的概念。
入度为0可以作为起点。
将所有入度为0的点加入队列queue
while queue不空
{
    t<-队头
    枚举t的所有出边，t->j
        删掉t->j这条边，并且将j的入度减1。
    如果j的入度为0，将j入队。
}
队列里的顺序即拓扑序。
（此题结果可能不唯一）

一个有向无环图，一定至少存在一个入度为零的点。
证明：反证法。