算法

AOV网与拓扑排序日常生活中常需要流程化的完成有依赖关系的事(比如“穿鞋前必须穿裤，穿鞋前必须穿袜”)。这类关系适合用有向无环图描述，其中的顶点表示任务，边表示任务之间的依赖关系。这个图之所以“无环”是因为如果存在环会导致任务“循环依赖”，导致环路上的任务无法找到可行的执行次序，即有环时这个图就没有意义。这样的描述任务依赖的有向无环图一般称为AOV网，在AOV网执行拓扑排序的结果是得到由AOV网所有顶点组成的序列，按该序列的次序执行任务不会违反依赖关系。 下面给出拓扑排序的定义“有向无环图上的拓扑排序(Topological Sorting)是将图的所有顶点排成有序序列，对于序列中的任意两顶点，若存在u到v的路径则v必然排在u之后”。 class AOV:def __init__(self): self.d… 阅读全文

无向图的连通性 1) 无向连通图：若无向图\(G\)上的任意两顶点间都有路径可达，则称\(G\)为无向连通图； 2) 割边(桥)：若删去连通无向图\(G\)的边\(e\)，则\(G\)不再连通，就称\(e\)是\(G\)的一个桥； 3) 割点：若删去连通无向图\(G\)的顶点\(u\)和以\(u\)为端点的边，则\(G\)不再连通，就称\(u\)是\(G\)的一个割点； 4) 无向的点双连通图：若从无向连通图\(G\)删去任意一个顶点剩下的部分还是无向连通图，即若\(G\)上不存在割点，则称\(G\)是一个无向的点双连通图； 5) 无向的边双连通图：若从无向连通图\(G\)删去任意一个变剩下的部分还是无向连通图，即若\(G\)上不存在割边，则称\(G\)是一个无向的边双连通图； 6) 子图：给定有向/无向图\(G’=(V’,E’),… 阅读全文

有向图的连通性 1) 转置图：把有向图所有边逆转方向得到的图； 2) 基图：有向图去掉边的方向后所得到的无向图； 3) 有向弱连通图：若有向图\(G\)的基图是无向连通图，则\(G\)为有向弱连通图； 4) 有向单连通图：若有向图\(G\)的任意两顶点\(u,v\)满足从\(u\)可达\(v\)或从\(v\)可达\(u\)，则\(G\)为有向单连通图； 5) 有向强连通图：若有向图\(G\)的任意两顶点\(u,v\)满足从\(u\)可达\(v\)且从\(v\)可达\(u\)，则\(G\)为有向单连通图； 6) 强连通分量(SCC)：有向图的一个极大的有向强连通子图，SCC最小为1个顶点，最大为整个图； 结合之前讨论的无向图连通性与上述定义，可了解有向图连通性的概念。下面研究SCC以及如何通过算法求出有向图上的全部SCC，这称为把有向图分解为SCC。通常把1个SCC记录为1个顶点集合。… 阅读全文

有根树的最近公共祖先(LCA)若有根树任意两点\(u,v\)都位于\(r\)点代表的子树中，则称\(r\)是\(u,v\)的公共祖先(\(r\)可等于\(u,v\)且\(u,v\)也可相等)，LCA是\(u,v\)所有公共祖先中，离\(u,v\)总距离最小的(设所有边的距离为1)，给出LCA的几个性质： 1) \(u,v\)的LCA是其所有公共祖先中深度最大的； 证明：设\(r\)是\(u,v\)的一个公共祖先，那么\(u,v\)距离\(r\)的总距离等于\(depth(u)-depth(r)+depth(v)-depth(r)\)。由于\(depth(u),depth(v)\)是固定的，所以\(depth(r)\)越大则说明总距离越小。 2) \(u,v\)的LCA有且仅有1个； 证明：若\(u,v\)有两个LCA，根据(1)其位于树的同层。由树性质，同层2个不同节点分别代表的子树一定无交集，导致矛盾。… 阅读全文

最小生成树网络是边有权重的无向连通图，最小生成树(MST)通常指无负权边的网络中，总边权和最小的生成树。MST有许多实际应用，如“已知任意城市间的距离，用总距离最短的公路连通所有城市”、“用最少长度的导线短接电路板的若干个点”。求MST的一般算法是Kruskal算法与Prim算法，其都为典型的贪心算法。给出几个较直观的引理： 1）包含网络全部顶点的无环连通图是该图的生成树 2）生成树的边数是顶点数-1。 3）生成树添加任意一条边后必然形成环。 4）若一个网络仅包含一个环，删除环上任意一边可得该网络的生成树。   Kruskal算法（并查集优化） 算法逻辑流程如下： 1）初始化含网络G所有顶点，但无边的子图G’，此时顶点就是连通分量。 2）从G中找权值最小（先把边权排序记录），且可连接G’某两个连通分量的边，将该边取出加入G’。… 阅读全文

单源最短路径单源最短路：对有向图\(G=(V,E)\)，边权\(w(E)\)，源点\(s \in V\)。求\(s\)到\(V\)任意顶点的最短路。 最优子结构：若\(s-a-…-b-t\)为\(s\)到\(t\)的一个最短路，则上述\(a-…-b\)必为\(a\)到\(b\)的一个最短路。 负权环路：求最短路时需考虑边权函数\(w(E)\)为负值时的一般化情景。若\(s\)到\(v\)的所有路径中存在负权重环路，由于可在环路上任意的刷低权重所以\(\delta(s,v)=-\infty\)。但本文将讨论的算法并不会去处理这种情况，只能接收从原点到目标点的所有路径中不存在负权重环路的图。本文认为这种情况下的最短路无意义。 一般环路：负权环路的情况已经被排除，正权环路显然不可能出现在任何最短路径的结果中。最后剩下0权重环路情况，若其出现在某个最短路径中出现0权重环路，那么必然可以从该最短路径中“删去”环路得到同样权重的路径。综上可以认为求所有路径中的最短路径可以转化为求所有无环路径中的最短路径。… 阅读全文

全源最短路径 全源最短路径问题是指给定带权有向图，求任意两点\(u,v\)从\(u\)到\(v\)的最短路径”。可把该问题直接作为\(|V|\)个单源最短路径问题，使用Dijkstra算法(二叉堆)的代价为\(O(|V||E|lg|V|)\)，Bellman-Ford算法的代价为\(O(|V|^2|E|)\)，对于稠密图二者的代价可分别写成\(O(|V|^{3}lg|V|)\)与\(O(|V|^4)\)。本文将讨论专门用于解决全源最短路问题的算法，这些算法大多基于邻接矩阵讨论，且不允许存在任何负权环路的。下面给出相关定义： 1) 带权邻接矩阵：带权有向图\(G=(V,E)\)与其权重可被\(|V|\times |V|\)的矩阵\(W\)描述。其中\(W_{ij}\)表示图边\((i,j)\)的权重，并且当\(i=j\)时有\(W_{ij}=0\)，当图边\((i,j)\)不存在时有\(W_{ij}=\infty\)；… 阅读全文