图结构

有向图与无向图数据结构中的图(Graph)是对数学分支图论(Graph Theory)中的图的表示，通常用二元组\(G=(V,E)\)定义图\(G\)，其中\(V\)是顶点的集合(顶点集)，\(E\)是边的集合(边集)。边集的元素也是二元组\((x,y)\)且\(x,y\)是\(V\)的元素，由于二元组包含\(x,y\)的序，若不关心\(x,y\)的序或用集合\(\{x,y\}\)表示边，则\(G\)是无向图，否则是有向图。一般按上图的方式“画”有向图和无向图。 直观上图是对前面讨论过的树的推广，树不允许树边任意的加在两节点间，图边则没有这些限制，并且图中一般不会指定“树根”这样的顶点。所以图相比树会有更多更复杂的“边界情况”，给出与之相关的概念： 1) 重边：即重复的边。设\(u,v\)是图顶点，对于有向图，若存在2个以上的从\(u\)到\(v\)的边，则称从\(u\)到\(v\)有重边。对于无向图，若存在2个以上连接\(u\)和\(v\)的边，则称\(u\)与\(v\)间有重边。也就是边集中有“相同”的二元组；… 阅读全文

广度优先搜索(BFS) 之前所讨论的BFS是种“简化的”版本，而“通用的”BFS将作为其他图算法的框架，所以在通用BFS的执行途中需记录一些信息。算法导论中的BFS需要记录顶点颜色(白/灰/黑=未到达/已到达/已到达且所有邻接顶点已到达)。顶点的\(\pi\)为前驱顶点，\(d\)为前驱顶点的\(d+1\)(源点的\(d\)为0)。在这种定义下顶点入队时从白染灰，出队时从灰染黑。BFS结束后利用顶点的\(\pi\)可得到该BFS下源点与其可达顶点形成的BFS树，树中的顶点为黑色而其他未达的顶点为白色。 def bfs(graph,vertex): visited = [vertex,] queue = [vertex,] while queue: vertex = queue.pop(0) for v in graph.getVertices(vertex):… 阅读全文

深度优先搜索(DFS) 通用DFS的用途比通用BFS更广泛，DFS记录顶点颜色、前驱、变灰时间、变黑时间。顶点有三种色(白/灰/黑=未到达/已到达并开始当前顶点的子DFS/已到达且全部邻接顶点的子DFS结束亦即当前顶点的子DFS结束)。时间的定义是每次变色时间加一，其用于描述搜索的推进。顶点由白变灰意味着其子DFS的开始，该DFS会一直持续到该顶点变黑。任意子DFS在结束时比开始只会新增染黑的顶点。DFS往往要求访问完源点所有可达顶点后(此时根据可达顶点的前驱可得DFS树)，若顶点集尚有未达顶点，就从中选新源点在“当前时间”继续DFS(最终根据所有顶点的前驱可得DFS森林)。该要求意味在解决很多问题时从任意源点DFS不影响结果，而且往往需访问所有顶点。 def _dfs(graph,vertex,time,attr):… 阅读全文

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\)；… 阅读全文