Graph & Tree

图论学习笔记

TYQ图论真是个渣渣呢

所以TYQ决定猛补图论

好的从0x60开始

表示博客园不用Latex真的烦呢QAQ，公式难打的要命QAQ

0x60~0x62

最短路讲解跳过

最小生成树：

Kruskal:

挺容易的，贪心的选最大值就好了

　　　　　　时间复杂度emmmO(mlogm)，适用于稀疏图

Prim

　　　　　　首先只在最小生成树中加入root节点

　　　　　　设两个集合S(剩余点),T(生成树)

　　　　　　每次找到两个点，使得他们的连线最短

　　　　　　时间复杂度O(n²)，多用于稠密图

例题

0x63~0x64

众所周知树是一种特殊的图，所以我们这里采用链式前向星存边

树的直径：

树形Dp:
demo:

void dp(int x){
    v[x] = true ;
    for(int i=head[x]; i;i = Next[i]){
        int y = ver[i];
        if(v[y])continue ;
        dp(y);
        ans = max(ans,d[x]+d[y]+edge[i]) ;
        d[x] = max(d[x],d[y]+edge[i])
    }
}
//本代码同算法竞赛进阶指南书中代码

两次Dfs/Bfs
从任意一个节点出发找到离他最远的点p
从p出发找到离他最远的点q
那么p到q为树的一条直径
demo

void dfs0(int step,int x){
      d[x]  = step ;     
      v[x] = true ;
      for(int i=head[x]; i;i = Next[i]){
           if(!v[i])
              dfs0(step+1,i) ;      
      }
      if(maxd<step){
            maxd = step;
            p = x ;
      }
}    
void dfs1(int step,int x){
      d[x]  = step ;     
      v[x] = true ;
      for(int i=head[x]; i;i = Next[i]){
           if(!v[i])
              dfs1(step+1,i) ;      
      }
      if(maxd<step){
            maxxd = step;
            q = x ;
      }
}

例题

LCA

找出x与y的最近公共祖先

暴力
从x节点向上跳，标记所有跳过的节点
再从y向上跳，遇到已标记的节点则停止
期望时间复杂度O(logN)，实际上珂以卡成O(N)
树上倍增法
设F[x,k]表示x的2^k辈祖先，若不存在则为0
我们执行一次广/深度优先遍历以求出F数组
然后就可以O(logN)回答询问了
tarjan算法
本质上是优化倍增法
离线算法，需要一次性读入全部询问
在tarjan算法执行的任意时刻，树上的节点分为三类：

已经访问完毕并且回溯的节点，标记值为2
已经开始递归，但尚未回溯的节点，标记值为1
其他节点，标记值为0

对于正在访问的节点x，他到根节点的路径已经标记为1
若y是已访问完的节点，则LCA(x，y)就是从y走到根节点的路程中第一个标记为1的节点
优化：当一个节点获得2的标记的时候，合并它所在的集合与它的父节点所在的集合
那么每次查询就可以直接使用getfa(y)了
时间复杂度为O（N+M），不会证
ST表：
dfs一遍，得到特殊的长度为 2*n-1 dfs序，然后维护一个在dfs序上的区间深度最小值，而拥有这个最小深度值的节点就是我们要求的LCA。
使用ST表预处理珂以O（1）回答询问
时间复杂度O（NlogN），且是在线算法
树链剖分：
树剖求LCA的速度还很快，O（N）预处理，O（logN）查询，相较于倍增LCA更快，而且求LCA那部分更好写，但是dfs部分比较难写.
树剖求LCA可能相较于倍增最大的优势是空间复杂度较低，只要O（N）
整个算法流程就是先树剖O（N）然后一个判断u与v是否在同一条重链，不在就往上跳，最后得到LCA，在就可直接得到LCA
至于为什么查询是O（logN）的，因为重链只有 logN 条，所以是O（logN）的
就是常数大点QAQ

树上差分

例题
我们定义一条附加边（x，y）覆盖的边为主要边构成的树中，x，y之间路径上的边
那么若第一步切断覆盖了0次的主要边，则可任意斩断一条附加边
若第一步切断覆盖了1次的主要边，则第二部方法唯一
若斩断覆盖了两次及两次以上的主要边则无解
那么问题就转化为给定一个无向图和一颗生成树，求每条主要边被附加边覆盖的次数
那么我们把一条附加边（x，y）覆盖改为把数上x，y两个节点点权加一，LCA（x，y）点权减一
最后进行遍历，求出F[x]代表以x为根的子树的节点点权之和
那么F[x]就是x与其父亲之间连边被覆盖的次数

基环树

树加上一条边
构成的环叫做基环
跟树差不多，但要先dfs找环，先考虑子树，再考虑环
可能以后会替代树？毕竟都在考仙人掌了
JZOJ考过

接下来我要换Markdown了QAQ

Link

引用：算法竞赛进阶指南

Warning!

本文由 TYQ 创作，采用知识共享署名 4.0 国际许可协议进行许可。
转载要与作者联系，并需在正文明显处署名作者且注明文章出处。
对了，我永远喜欢C++啊。