树是无环连通图
图分为两种，一种是有向图例如a -> b 另外一种是无向图，a-b。
有向图就是记录从a到b的路径，无向图就是从a 到b可以，b到a也行，所以在存储无向图的时候就是存两个有向图，分别是a -> b 和 b -> a。
存储有向图的方法有两个一个是邻接矩阵，就是开一个二维数组，表示从a 到 b的边，如果存在存1，不存在存0，如果有权重就存权重。这种适合存比较稠密的图，比较稀疏的适合用邻接表

另外一种方法是邻接表，就是每个点都开一个单链表，用h[]，表示表头，初始化的时候指向-1，数量级就是N(全部数据的个数)

memset(h, -1, sizeof h); //在头文件cstring中

之后每次存一个边，例如a - > b, 就在表头为a的单链表上从表头处插入b，单链表中存的值就是表头指向的那个点，其中每个单链表都是无序的，这个顺序也没有意义，因为当遍历的时候每次都将遍历到的e[]，值作为一个头节点去遍历，表示的是遍历到的这个点之后指向的其他点，所以单链表是不存路径的，只是存单向边。

插入表头的方法，定义一个idx，表示当前可以用的下标，e[], 表示值，ne[]，表示指向的值（即指向下一个数的指针），e[idx] = x, ne[idx] = h[表头]， h[当前的表头] = idx++. 其中e[], ne[] 数量级可以开两倍的N，防止越界

深度优先遍历（即深搜dfs）

因为一般的题目每个点只会遍历一次，所以要开一个布尔数组st[N], 来存放是否遍历过

void dfs(int u ) // u 表示开始的点
{
    st[u] = true ; // 标记u以及遍历过
    for (int i = h[u]; i != -1; i = ne[i]) // u开始所以作为头节点，ne和h都是表示的是指向下一个数的指针
    {
        j = e[i] // 将值赋给j，j表明下一个遍历到的点，然后判断是否遍历过，若没有则递归dfs
        if (!st[j]) dfs(j);
    }
    
}

例题：

树的重心

给定一颗树，树中包含 n个结点（编号 1∼n）和 n−1 条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式
第一行包含整数 n，表示树的结点数。
接下来 n−1行，每行包含两个整数 a和 b，表示点 a和点 b之间存在一条边。
输出格式
输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。
数据范围 1≤n≤1e5

输入样例：

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

输出样例：

4

思路：
利用dfs，每次都将遍历到的点，删除后，连通块的最大值求出，之后只要是将所有点代表的最大值的最小值求出就行。
如何求每个点删除之后的连通块的最大值，这里先是新建一个变量sum，表示的是这个点所连通的所有点的数量，一开始让 sum = 1, 表示只有一个点，之后让每次dfs完成之后返回一个sum，表示的是从某个点开始到所有可以遍历的点的数量，理论上，一开始是只有一条线，但是由于是有迭代，每个点的sum都加等于那个点之后每条线的点的数量，所以最后返回的sum就是那个点往下所连的点的数量（包括他本身，以及因为他不能向上回溯，只有下面的点回溯到他，所以sum是只包括了他本身，以及之后所连所有点的数量）。再新建一个变量res，这个变量要放在dfs函数中，表示的是每一个有一个单独的res（如果是放到外面，当迭代回溯的时候原来的那个res会变，而res不止比一次，而是有多少个子节点就比几次，所以在内存中这个正在遍历的点的res应该要被保留），当下一次dfs开始时 = 0初始化，表示的是这个点删除之后，最大的联通块所包含的点的数量，很显然，这个连通块分为两个部分，一个是这个点之后的连通块，以及这个点上面的节点所连接的连通块，之后的连通块其实就是dfs的返回值，所以用res = max{res, s},就是用当前的res和后面返回的s进行比较然后更新。
上面的连通块其实就是用全部个个数减去这个节点连接的后面的节点的个数（包括他本身，因为他被删除了），所以用n - sum ，之后就是更新res。完成之后res存的就是当前这个节点的最大连通块的值，之后更新答案只要是比原来的ans小就保存。ans = min(ans, res) // min和max在头文件algorithm中

重边 指的是有两个或多个重复的边，例如a -> b 有两个
自环 指的是一个元素的一条边指向自己，例如 a -> a
所有边的长度都是1，指的就是可以用宽搜来求最短路，否则可能要用动态规划（DP）

广度优先遍历（bfs）

和之前的bfs思路一致，用到的数据结构是队列，只不过是在图中进行的。
先是用邻接表来存图，

int h[N], e[N], ne[N], idx;
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

bfs中队列还是用数组来模拟

int d[N]; //表示的是起始点到某个点的距离
bool st[N]; //第一次遍历为最小值，所有要加一个判断
int q[N]; //模拟的队列

int bfs()
{
    int hh = 0, tt = -1;
    q[++tt] = 1; //看题目要求加入起始点
    st[1] = true;
    memset(d, -1, sizeof d) //初始化d,表示还没开始计算距离
    d[1] = 0; //初始化
    while(hh <= tt)
    {
        int t = q[hh++]; //取队头
        // 这边如果是矩阵的话就是要遍历四个点，但这个用的是邻接表，所以也要用邻接表的遍历方法来遍历,判断条件一样也是在遍历之后，如果符合条件就放到队列中，之后就是循环继续从上一个最先放进去的点开始，表示进行到下一层
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(!st[j])
            {
                st[j] = true;
                d[j] = d[t] + 1;
                q[++tt] = j;
            }
        }
    }
    return d[n]
}

例题：

图中点的层次

给定一个 n个点 m条边的有向图，图中可能存在重边和自环。
所有边的长度都是 1，点的编号为 1∼n。
请你求出 1号点到 n号点的最短距离，如果从 1号点无法走到 n号点，输出 −1。
输入格式
第一行包含两个整数 n和 m。
接下来 m行，每行包含两个整数 a和 b，表示存在一条从 a走到 b的长度为 1 的边。
输出格式
输出一个整数，表示 1号点到 n号点的最短距离。
数据范围 1≤n,m≤1e5
输入样例：

4 5
1 2
2 3
3 4
1 3
1 4

输出样例：

1

思路：求最短距离，然后所有边的长度为1，所以可以用广度优先遍历bfs。在输入的时候要记得，读入的是边，不是点。

在读双边的时候数据大小应该差不多是4N,因为单边是2N,双边差不多有两倍所以占4N.