话不多说，进入正题。

树和图的存储与遍历

树和图的存储

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

1. 有向图 a—>b
2. 无向图 a<–>b,无向图也就是特殊的有向图

所以只需要知道有向图的存储方式即可。

有向图的存储方式：

• 邻接矩阵 ,g[a][b]存储a到b的边的信息，如有权重就存储权重；没有则是bool值。占用空间n^2,过大，不常使用。
• 邻接表 ,每个点都会拉一条单链表，如同哈希表的拉链法，单链表存储该点与其他哪些点相连。存储的次序无关紧要。

树和图的遍历

1. 深度优先遍历
2. 宽度优先遍历

深度优先遍历

找一个起点，从这个起点开始一条路走到黑。每个点只遍历一次。
遍历框架：

#include<bits/stdc++.h>
using naemespace std;

const int N = 100010,M = N*2;
int h[N],e[M],ne[M],idx;
bool st[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=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);
    }
}

int main()
{
    memset(h,-1,sizeof h);

}

宽度优先遍历

距离从小到大来遍历，取第一次遍历到的结果（每个点只遍历一次）。
遍历框架：

队列初始化
while(queue 不空)
{
    取出队头
    拓展队头所有邻点x
    if(x未遍历)
    {
        x入队
        d[x]=d[队头]+1;
    }
}

收工！