图论及其应用

图论及其应用山东省青岛二中王元炜图论及其应用图的定义有向图无向图特殊的图——树图的最短路算法dijbellman-fold(spfa)floyed图的生成树primkruskal潴留算法有向图的强连通分量tarjan算法有向图的拓扑序拓扑排序图的定义1.定义图G={V,E}V代表图的顶点集合，E代表图的边的集合。2.对于有向图，E中的每个元素是由有序点对<p,q>构成，代表p->q的一条边。3.对于无向图，E中的每个元素是由无序点对(p,q)构成，代表p和q之间的一条边。4.如果一个无向图满足|E|+1=|V|并且联通，那么我们成这个图是一棵树5.所有边都没有权值或者权值都相同叫做无权图，否则叫做有权图。图的最短路图的最短路在实际应用中非常多我们说的图的最短路默认为有向图，对于无向图可以理解成每条边分成两条边，方向相反权值相同。简单就是说从一个顶点出发，经过一些列边的集合，到达另外一个点。这些边的权值加起来最小最短路算法对于一个无权图，那么可以使用宽度优先搜索(bfs)进行得到答案时间复杂度O(n)最短路算法如果我们需要知道所有的点对之间的最短路，可以使用floyed的传递闭包方法。floyed算法思想：我们每次选择一个中间点，然后枚举起点和终点，用通过中间点的最短路径更新起点和终点之间的最短路径时间复杂度O(n^3)floyed代码实现代码非常简单注意枚举顺序最短路算法如果我们只需要知道从一个点出发到其他点的最短路，而且图中的边权全部为正，我们可以使用dijsktra算法。算法思想：我们每次选择一个距离原点最近而且没有被访问过的点，然后我们访问这个节点，并且用这个点的所有出边去更新其他所有节点从原点出发的距离，重复此算法直到所有点都被访问过为止时间复杂度O(n^2+m)使用堆和临街表优化可以做到O(nlogn+nlogm)dijsktra算法代码实现dijsktra算法代码实现使用堆优化Bellman-fold算法(spfa)如果图中出现了负权变，甚至有可能出现负权环（此时最短路不存在）。其他两个算法就不再适用。这里我们介绍bellman-fold算法bellman-fold算法将判定一个图是否存在最短路，如果存在则返回，否则返回不存在最短路Bellman-fold算法(SPFA)算法思想：我们将算法进行n此，每次从所有点出发更新所有后继节点的最短路情况如果所有节点都没有被更新则返回最短路，如果第n此依然更新，那就返回没有答案时间复杂度O(nm)对于一个队列进行优化的方式，我们每次更新一个点就把这个点加入队列，每次从队列里面更新。这个优化，对于一般的图来说辅助度是O(Km)的K是常数SPFA算法实现小试身手在平面上有n个点，每个点都有坐标(x,y)我们每次可以从点A到达点Ｂ，的条件是A,B之间的距离不超过L,给定n,L,和每个点的坐标，求从一号点到达n好点的最短距离n<=1000小试身手直接暴力求出任意两点之间的距离还是不可达，然后使用Dijsktra算法即可小试身手给你一个平面，上面有n个点，每个点有坐标(x,y)从一个点A到B的距离定义为D=min(A.x-B.x,A.y-B.y)求1-n的最短路n<=1000howaboutn<=100000小试身手默默的等式小试身手默默的等式，和今天的T2类似，还是在取模的意义下建图。小试身手对于n<=1000我们依然可以直接暴力建出图来进行Dijsktra算法但是对于n<=10000的测试点，所有边一共有10^10条，我们无法存下来但是我们发现，只有x坐标相邻和y坐标相邻的边才有意义(为什么？)，然后就可以建出图来用堆优化的Dij或者spfa过掉小试身手给你一个n个点的图，小Q有q个询问，每次询问任意两点之间的最短路n<=200,q<=4000000小试身手显然每次使用Dijsktra是不可能的注意到我们关心的是任意两对之间的最短路使用floyed预处理，每次询问O(1)回答即可复杂度O(n^3+q)图的生成树对于一个连通图G={V,E}定义图的生成树G'={V,E'}其中E'∈E，|E'|=|V|+1,并且G'联通那么G'就叫做G的一个生成树生成树的性质生成树有n个点和n-1条边构成，并且联通生成树保留了原图的最精华的信息（至于为什么之后会说到）生成树任意两点之间有且仅有一条路径最小生成树对于G的所有生成树，边权和最小的生成树称为最小生成树求最小生成树的算法：Prim&Kruskal这两个算法的本质就是贪心至于贪心为什么是对的这里不讲了理解思想就可以了Prim算法及思想首先我们将V分成两部分U,SU∩S=∅U∪S=V一开始S中只有任意以个节点每次我们枚举每条U，S之间的边权最小的边S中这条边的端点删除并加入U我们可以每次更新S中点的这个值不需要每次枚举边复杂度O(n^2)如果使用堆优化可以做到O(nlogn+nlogm)Prime的代码实现kruskal算法思想我们把所有边按照权值从小到大排序然后枚举每条边，顺次加入最小生成树，如果这条边加入之后依然可以形成最小生成树就加入，否则就跳过第二步的询问可以用并查集维护做到O(nαn)kruskal算法实现算法比较Prim只能求出最小生成树的权值，无法得到具体的形态而Kruskal可以求出形态，所以建议使用KruSkal小试身手有n个点m条边，求n->m的一条路径使得边权最大的那条边最小n,m<=100000小试身手用kruskal求出最小生成树然后求最短路即可（此时最短路的定义有变化但是依然可以求出）小试身手NOIP2013Day1T3给你一个图，有Q此询问，每次询问任意两点之间边权最大路径的最小值小试身手求出最小生成树然后使用倍增算法快速求出路径的值小试身手USACO2008Oct灌水Farmerjohn有一个农场需要灌溉，首先我们序号给一个位置引水需要一定的花费，然后任一两块农田之间连接水渠也有一定的花费，求全部灌溉的最小花费n<=1000小试身手首先建立一个超级原点，和所有点连边权值是饮水的代价，然后求最小生成树即可其他最有比率生成树最小乘积生成树潴留算法强连通分量对于一个有向图G的一个导出子图G'={V',E'}到处子图的定义是：其中V'是V的子集，当且仅当对于任意<x,y>∈E且x∈V',y∈V'则<x,y>属于E'如果该导出子图中任意两点可达，则成为G'是G的一个强连通分量如果G'是G的一个强连通分量，且不存在一个H是G的强连通分量满足G包含于H，G是一个极大强连通分量强连通分量的性质 强连通分量之间任意两点互相可达，任意两个强连通分量之间的关系是拓扑的Tarjan算法Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。tarjan算法定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出Low(u)=MinDFN(u),Low(v),(u,v)为树枝边，u为v的父节点DFN(v),(u,v)为指向栈中节点的后向边(非横叉边)当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。tarjan算法tarjan算法拓扑排序每次选择一个入度