树是一种特殊的图

一. 图的基本介绍

图分为有向图和无向图
有向图就是两条边之间连了一个箭头,只能按箭头的方向走
无向图就是只有连边,没有方向,想往哪里走就往哪里走
无向图可以看成特殊的有向图
想让有向图变成无向图只需要多连一条边(2个点)就行了

二. 图的存储

因为无向图是特殊的有向图,所以只需要考虑有向图的存储
可以用邻接矩阵和邻接表存
邻接矩阵用的较少，一般存储稠密图
邻接表是 $n$ 个单链表
内部存的是这个点能到达的点
如果要插入一条新的边,那么就插到那条边对应的单链表里，一般在头插

三.深度优先遍历

深搜和宽搜就不用多说了
这里注意每个点遍历 $1$ 次
模板

void dfs(int u){
    st[u]=true;
    for(int i=h[u];i!=-1;i=ne[i]){//遍历一下u的初边
        int j=e[i];//编号
        if(!st[j]){//如果没被搜过
            dfs(j);//一条路走到黑
        }
    }
}