文章来源: http://thunderfyc.wordpress.com.cn/ 

VI Graph Algorithms
  22 Elementary Graph Algorithms
    Representations of Graphs
      邻接表 一个结点拖张表 为其连边
      邻接矩阵 n*n的表 g[i][j]表示边i-j
      边集数组 一个数组元素为边

    点的标记 白色为未访问 灰色为访问到 黑色为所有孩子都访问完

    Breadth-first search
      宽度优先搜索 从一点开始 将其放入队列尾 取出队首元素 查找射出的边 将未访问过的另一个元素 放入队尾 弹出队首
      Shortest Path 从源到结点的最少边数 BFS遇到结点所需的层数 就是SP

    Depth-first search
      对于结点 查找边 然后访问边那头的结点 递归操作  也可用栈实现
      对于结点 第一次接触时的编号为前序编号 最后一次接触的编好为后序编号

    图中边的类别 Tree Edge 搜索树种存在于图中的边 Back Edge 递归结束返回祖先的边 Forward Edge 祖先连接后裔的非树边 Cross Edge 其他所有边
    被访问后继点为白 Tree Edge  灰 Back Edge 黑 Forward Edge、Cross Edge

    Topological Sort
      以有向图来表示工序安排 当工序需要前序工作时 被射入一条边 最后的工序安排即为拓扑序列
      用DFS求后序编号 倒序输出即为拓扑序列

    Strongly Connected Components
      有向图的一个子图 能够满足任意两个结点可以互相访问
      求后序编号 将图所有边反向 反复从没有访问过且后序编号最大的结点开始DFS 能DFS到的都为一个强连通分量

    Articulation points, bridges, and biconnected components
      Articulation points 是去掉之后 G就不连通的点
      Bridge是去掉后 G就不连通的边
      Biconnected Components 是一个最大边集 其中任意两条边在一个环上
      求关节点的时候 DFS一下 一个结点是关节点有且仅有以下情况 1 DFS树根有至少两个孩子 2 如果非根 所有子孙没有指向其祖先的后向边
      判断是否有指向祖先的后向边 DFS时记录结点深度 另外记录结点当前祖先深度 DFS到一个结点时 查找有无指向祖先（此时标记为灰）的边 若有 且指向祖先早于当前结点祖先则更新 然后访问孩子 访问完后若孩子的祖先深度小于结点祖先深度则更新结点 如果孩子的祖先深度不小于结点深度 就是关节点
      求桥的时候 如果孩子的祖先深度大于结点的祖先深度 那么这条边为桥
      双连通部分为非桥的边

    Euler Tour
      在有向图中遍历每个边恰好一次的回路
      所有点的出度等于入度才存在 任意一个点 找后继插入 走一条边删一条边 直到回到这个点 这条路径记录下来 继续重复 直到没有边为止

    Reachability
      有向图中 求从某个节点射出边能够达到的结点里编号最小的一个
      做反向图 然后做DFS 从最小编号点开始向下访问一层 其最小值均为此 然后继续

文章来源: http://thunderfyc.wordpress.com.cn/

  23 Minimum Spanning Trees
    图中 将所有的点连接起来的 n-1条边 的权的和 最小的边集
    Kruskal算法 将边按权排序 加入第一条边之后 如果下一条边的两个结点不在同一连通分量中 就加入这条边 两个连通分量合并 用并查集实现
    Prim算法 集合初始为任一顶点 然后在集合中查找某个结点与集合外结点的边权值最小的那个  把外界结点加入集合 边为MST的一条 用堆实现

    Second-best minimum spanning tree
      次小生成树 除掉MST之后最小的生成树
      1 Prim同时记录max[u][v]表示从u到v路径中最大的边权 枚举不在MST中的g[u][v]必然大于max[u][v]替换之 找到g[u][v]-max[u][v]最小的即可
      2 Kruskal后枚举MST中的边 去掉后重新求MST 找其中最小的一个

    Minimum Spanning Tree in Sparse Graphs
      稀疏图的最小生成树
      将图中每个结点访问 如果结点没访问过 就查找最短边 加入访问集 构造新图 点集为访问集中的连通分量 对于每个原来边集中的边 判断两端点 如果连通分量没连 将连通分量代表元素的边加入边集 如果连了 判断原来的点的距离是否比连通分量代表元素距离小 如果是 则修正 然后得到的新图做MST之后合并第一次得到的边即可
      简单的说 就是用连通分量作MST 保证连通分量的边都为需要

    Bottleneck Spanning Tree
      生成树的最大边权是所有生成树中最小的 生成树的瓶颈指生成树中的最大边权
      最小生成树是瓶颈生成树

    Chapter notes
      贪心能够完成MST的原因是 查找MST满足图的矩阵胚 判断一个树是否是MST 用类似线性查找的算法 一个递归获得不可能在MST中的边 另外一个递归求剩下的里的MST

  24 Single-Source Shortest Paths
    最短路径 一条边权值和最短的路径
    分类 单源最短 单汇最短 单对结点最短 每对结点最短
    负权边 如果任何一个环的值正 成立 否则可以不停绕负环
    环 最短路既无正环 也无负环 一个最短路最多有n-1条边
    松弛 如果A到B的距离加上B到C的距离 小于A到C的距离 那么松弛

    Bellman-Ford
      A固定 枚举B和C 不停的做松弛 直到不能松弛为止 路径最长为n-1 所以最多做n-1次松弛 如果还能松弛就有负环
      有向无环图 按照拓扑顺序进行松弛 不须迭代
      Critical path 有向图中的边表示某工作必须在另外一个工作之前完成 那么一条最长的路径 满足工序所要的顺序 路径长度为完成的时间下限

    Dijkstra
      在已访问集合中找到向外连的最短边 然后把那个点加入 枚举目标点 用这个新点作松弛 用堆优化

    Different constraints and shortest paths
      Linear programming
        m*n的矩阵A 一个m向量b 一个n向量c 找到n个元素的向量x 使得sigma(ci*xi)最大 并且满足 Ax<=b
      System of difference constraints
        A中每行只有一个1和一个-1 其他为0 即满足若干大小关系xi-xj<=bk
        建图 T到所有点射出权为0的边 如果xi-xj<=bk则j到i射出bk 最后0到其他节点的最短距离为一组解
        0到i的距离要小于等于到j的距离加上边的权值  显然是最短路

    Yen’s improvement to Bellman-Ford
      对于DAG 将图的点拓扑排序 边分为两组 和拓扑顺序的一组边 逆序的一组边 然后顺序访问所有结点 从该点出发的顺序边松弛 再逆序访问所有结点 从该点出发的逆序边松弛

    Nesting boxes
    Arbitrage
      请看UVA题解

    Gabow’s scaling algrithm for SSSP
      将边的权的二进制位数设为k 然后第i次做前i二进制位 第一次用O(E)时间 一个优先队列Q[i]存储目前到达路径长度为i的结点  然后建立w’i(u,v) = wi(u,v)+2d_i-1(u) - 2d_i-1(v) 这个新图做Dijkstra O(E) 得到d’ 那么di(u) = d’(u)+2d_i-1(u)

    Karp’s minimum mean-weight cycle algorithm
      有向图一个环的权和除以边数 得到平均值的最小
      Di(x)表示图外源点到点x长度为i条边的路径最小值 最小环平均值 为(Dn(v)-Dk(v))/(n-k) 枚举k中最大值之后再枚举v的最小值

    Bitonic shortest paths
      一个序列经过或不经过环状变化后 先单增再单减 要求一个有向图的最短路径上的边权 形成Bitonic Shortest Paths
      第一次按照升序松弛所有边 然后按降序松弛 再重复

  25 All-Pairs Shortest Paths
    求所有点对的最短路径
    输出的时候用pre[i][j]表示i到j的路径中 j前一个结点

    Shortest paths and matrix multiplication
      长度为m的任两点路径形成的矩阵 l_m[i][j] = min{l_m-1[i][k] + w[k][j]}
      和矩阵乘法的形式类似 l_0 = w;  l_m = w^m
      加速 二分求w^n

    The Floyd-Warshall Algorithm
      枚举中间结点 从1到n 然后枚举要松弛的i-j 如果g[i][j]<g[i][k]+g[k][j] 松弛
      路径中如果有k 那必然要塞入 如果没有k 在k’中g[i][j]会更新  如果插入k之后 i-k或者k-j中有k’ 以k-j为例那么因为g[i][k']中有k 则i-k’以求得 k’-j无k 假设以求得(否则就是另外一个这个问题) 那么即可得到k’-j i-j的路径必然能得到最优的
      求路径 记录i-j中间的k 如果无则为0 求i-j的路径就变成 i-k和k-j的路径

    Transitive closure of a directed graph
      从某点能否到另外一点
      用Floyd-Warshall 如果有路径为1 无路径为0 松弛操作为 如果g[i][j]=0 且 g[i][k]=1 g[k][j]=1 则g[i][j]=1

    Johnson’s algorithm for sparse graphs
      设立新的源 到所有点的距离为0 然后用Bellman-ford求源到所有点的最短距离h 然后每条边的新权为w’[i][j]=w[i][j]+h[i]-h[j] 使得权为正 对于每个节点 在新图上作Dijkstra 然后得到的最短路径+h[j]-h[i]即可

    Transitive Closure of a Dynamic Graph
      每增加一条边 就更新一次图的连通状况
      枚举i 如果g[i][u]=1 和g[i][v]=0 枚举j 如果g[v][j]=1 则g[i][j]为1 总时间为O(n^3)

  26 Maximum Flow
    每条有向边有容量 求从源点到汇点的最大流量 结点不滞留流量
    Networks with multiple sources and sinks
      添加超级源射向所有源 容量无穷 添加所有汇射向超级汇 容量无穷

    The Ford-Fulkerson Method
      只要存在增广路 就改进

      Residual networks 剩余网络
        如果产生一套可行流 那么就将流的方向取反之后边容量加上此上的流量 同向的减去确定的流量 形成新图叫剩余网络 取反是为了能够必要时减小以确定的通过流量

      Augmenting Paths 增广路
        当存在从源到汇的简单路径就是增广路

      Cuts of Flow Networks 割
        割是把图的点集分为两个部分 源汇不通 割的容量为两部分之间所有的连边容量和

      最小割等于最大流

      The basic Ford-Fulkerson Algorithm
        每次找一条路径 然后找到路径瓶颈容量 构造剩余图  O(FE)

      The Edmonds-Karp Algorithm MPLA 最短路径增值
        在找路径时 用BFS求边数最短路径 O(V E^2)
        BFS O(E) 瓶颈边存在E条 每条边最多做V/2-1次瓶颈(作了一次瓶颈之后 消失 然后有人访问逆向边 又出现 总共V/2对这样的情况) 所以O(V E^2)

    Maximum Bipartite Matching
      两排点 互相有边 找到最多数目的一组边 满足任意两边没有公共点
      超级源射入左排 右排射入超级汇 然后做最大流 最大流的最大值F = O(V) 时间为 O(VE)

    Push-relabel Algorithms O(V^2 E)
      假设源的高度为V 汇的高度为0 每个结点附带流量库储存多余流量 往源里猛灌流量 每条边都补满 不停的找流量库非0的结点 结点只能从高流向低 如果边导向的点均比自己高 就提升自己 做出剩余图(反方向加容量)

    The relabel-to-front algoithm O(V^3)
      维护一个处理序列 对于序列上的点 进行操作 只要流量库中还有流量 就对射出结点进行填充 找不到点的话 就提升自己 如果提升过自己 结点提前到维护队列首 然后访问后一个结点
    Send to School
      俩孩子互相不喜欢 不愿意在另外一个孩子走过的街道上走路 但是可以在同一个交叉路口 家和学校都在交叉路口上 求走路方案
      每个交叉路口作结点 家和学校为源汇 有路就加容量为1的边 如果最大流为2 可行

    Edge Connectivity
      一个无向图中移走最少的边使其不连通
      任意取一点做源 然后枚举其他的点作汇 无向变双向有向 求最小割 然后在最小割中取最小的

    Escape problem
      一个方格盘 在上面有若干特殊格点 判断能否从边界若干点沿格线到达格点 路径无公共点
      建图 格点为结点 边界点为多源 特殊格点为多汇 边容量为1 存在满流即可

    Minimum Path Cover
      一个有向无环图中 若干不相交的路径（或单结点路径）覆盖所有点
      建图 超级源射向N个点 另外N个点射向超级汇 两组点之间 如果有边 则连边 容量为1 最后求最大流
      路径最少 则覆盖边尽量多 未用的边尽量少 最大匹配满足

    Space Shuttle Experiments
      有若干试验 每个试验能够有若干收益 需要若干工具 每个工具需要花费 求最大收益
      建图 超级源射向所有工具 容量为花费 所有试验射向超级汇 容量为收益 工具和试验有关系就连边 容量为无穷 求最小割(也就是最大流) 和汇联通的试验均为要求
      因为最小割不可能是无穷的边 所以如果一个试验连着汇 必然试验所需器材都联通 因为切割耗费最小 工具花费算在切割中 被放弃的收益也在切割中 实际收益=总收益-放弃收益-花费 最小割=放弃收益+花费 那么最小割最小 实际收益最大

    Maximum flow by scaling
      找到比最大容量小的2次幂 然后只要存在该2次幂的路径则填充 否则幂减半 时间O(E^2lgC) C为最大容量

    容量有上下限的流
      每条边有最小流量和最大流量限制 所以导致最后可能没有流
      建图 超级源射向每个点 每个点射向超级汇 原来的源汇互射 新图原来边容量为上下界之差 超级源射出为该点接受边下界和 超级汇受到边为该点射出边下界和 源汇流量无穷 存在流的条件是超级汇受到边均饱和

    The Hopcroft-Karp Bipartite Matching Algorithm O(sqrt(V)*E)
      增广路径为两端点节点未被匹配 途中路径为在匹配中和不在匹配中交替 这样可以通过匹配和未匹配交换 使匹配数加一

文章来源: http://thunderfyc.wordpress.com.cn/