咕了两个月的我（如果不算Luogu的题解）终于回来写博了qwq，因为我的数据结构知识一直很薄弱，每次考试老是失分，所以我决定写一写关于图论的博客，最近一段时间也正好在复习这部分，这篇博客的内容会涉及到：树与图的遍历，树的深度，图的联通块，拓扑排序，树的重心，最短路，最小生成树，并查集，Tarjan与图的连通性，树的直径，LCA，树链剖分，负环。文章内容与lyd的《算法竞赛进阶指南》重合度比较高（因为我就是按照他的书来复习的），同时文章以讲解为辅，代码为主，适合各位同学复习而并非初学者接触。

所有模板都是我手打的，也许有错误，欢迎批评指正弱弱的我qwq。

声明

博客中如果没有特殊说明，则默认是n个点和无向图，文中会使用vector，邻接表，邻接矩阵这三种方式来存储。

树与图的遍历

树与图的存储方式是相同的，遍历可以采用dfs和bfs这两种方式。

深度优先遍历与深度

众所周知写这个只是为了知识的完整性，大家随便看看就行。

dep是深度数组。

void dfs(int u)
{
    vis[u]=true;
    for(int i=h[u];i!=-1;i=e[i].nxt)
    {
    int v=e[i].v;
    if(vis[v])    continue;
    dep[v]=dep[u]+1;
    dfs(v);
    }
}

广度优先遍历

bfs并没有dfs常用，用队列q来存储，每次遇到一个节点u，就入队，然后依次入队它的子节点，如果子节点也全部入队，就把u出队，又入队它第一个子节点的所有子节点，以此类推...

eg:

入队标蓝，出队标红，这张图的bfs模拟过程如下：

1 234

234 5

345

45 6

56 7

67 8

78 9

代码的实现很简单。

void bfs()
{
    memset(d,0,sizeof(d));
    q.push(1);
    d[1]=1;
    while(!q.empty())
    {
    int u=q.front(),q.pop();
    for(int i=h[u];i!=-1;i=e[i].nxt)
    {
    int v=e[i].v;
    if(d[v]) continue;
    d[v]=d[u]+1;
    q.push(v);
    }
    }
}

我们可以看到图中有一个d数组，d[u]的作用是存储从1遍历到节点u所需经过的最少点数，qwq但是请大家不要妄想能用这个来求最短路，stO青君大佬。

bfs的遍历有两个性质：

1.在访问完节点i的所有节点后，才会开始访问节点i+1。

2.队列中的元素至多有两个层次的节点，第一部分属于i层，第二部分属于i+1层，所有i的节点排在i+1的节点之前，也就是说，bfs遍历满足两段性和单调性，这也是它的基本性质。

树的dfs序

一般地，我们在dfs时，在刚进入递归前和即将回溯之前各记录一次该点的编号，最后产生的2n长节点的序列就是dfs序，如果用a[N>>1]存储dfs序，l[ ]和r[ ]分别存递归前和回溯前的cnt，a[ l [ u ] ]和a[ r [ u ] ]这一段记录的就是u节点的子树，由此可以很好地把树上操作转化为区间问题~！

代码简短也好理解。

void dfs(int u)
{
    vis[u]=true;
    l[u]=++cnt;
//    a[cnt]=u;
    for(int h[u];i!=-1;i=e[i].nxt)
    {
        int v=e[i].v;
        if(vis[v]) continue;
        dfs(v);
    }
    r[u]=++cnt;
//    a[cnt]=u;
}

树的重心和子树大小

如果一棵树有v1~vk个节点，并且以v1~vk为根的子树大小是siz[v1]~siz[vk]，那么以u为根的子树大小是siz[u]=siz[v1]+...+siz[vk]，也就是说siz数组用来存储节点的子树大小（包括节点本身）。

树的重心指的是，如果我们把一个节点u从树中删除，那么原来的一棵树可能会分成若干个不同的部分，如果在删除一个节点后，剩下的所有子树中最大的一棵是最小的，那么这个被删去的节点称为树的重心，对于无权图，大小一般指的是节点个数。

代码简短好理解，如下。

void dfs(int u)
{
    max_point=0;
    siz[u]=1;
    vis[u]=true;
    for(int i=h[u];i!=-1;i=e[i].nxt)
    {
        int v=e[i].v;
        if(vis[v]) continue;
        dfs(v);//要先遍历子节点才能找到子节点的siz值 qwq为什么总是忘记dfs 我有罪 
        siz[u]+=siz[v];
        max_point=max(max_point,siz[v]);
    }
    max_point=max(max_point,n-siz[u]);
    if(max_point<ans)
    {
        ans=max_point;
        pos=u;
    }
}

图的连通块划分

经过多次dfs，可以找出一张图的每一个连通块，不会连通块的同学可以去看看知识点再做两道题，这个很简单，不赘述了。

void dfs(int u)
{
    scc[u]=cnt;
    for(int i=h[u];i!=-1;i=e[i].nxt)
    {
    int v=e[i].v;
    if(scc[v]) continue;
    scc[v]=cnt;
    dfs(v);
    }
}
int main()
{
    for(int i=1;i<=n;i++)
    if(!scc[i]) dfs(i);
}

节点