Browsed by
Category: GraphTheory

[转载]有向图强连通分量的Tarjan算法

[转载]有向图强连通分量的Tarjan算法

转自:https://www.byvoid.com/blog/scc-tarjan [有向图强连通分量] 在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。 下图中,子图{1,2,3,4}为一个强连通分量,因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量。 直接根据定义,用双向遍历取交集的方法求强连通分量,时间复杂度为O(N^2+M)。更好的方法是Kosaraju算法或Tarjan算法,两者的时间复杂度都是O(N+M)。本文介绍的是Tarjan算法。 [Tarjan算法] Tarjan算法是基于对图深度优先搜索的算法,每个强连通分量为搜索树中的一棵子树。搜索时,把当前搜索树中未处理的节点加入一个堆栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。 定义DFN(u)为节点u搜索的次序编号(时间戳),Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出, Low(u)=Min { DFN(u), Low(v),(u,v)为树枝边,u为v的父节点 DFN(v),(u,v)为指向栈中节点的后向边(非横叉边) } 当DFN(u)=Low(u)时,以u为根的搜索子树上所有节点是一个强连通分量。 算法伪代码如下 tarjan(u) { DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值 Stack.push(u) // 将节点u压入栈中 for each (u, v) in E // 枚举每一条边 if (v is not visted) // 如果节点v未被访问过 tarjan(v) // 继续向下找 Low[u] = min(Low[u], Low[v]) else if (v in S) // 如果节点v还在栈内 Low[u] = min(Low[u], DFN[v]) if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根 repeat v = S.pop // 将v退栈,为该强连通分量中一个顶点 print v until (u== v) } 接下来是对算法流程的演示。 从节点1开始DFS,把遍历到的节点加入栈中。搜索到节点u=6时,DFN[6]=LOW[6],找到了一个强连通分量。退栈到u=v为止,{6}为一个强连通分量。…

Read More Read More

HDU 1142 A Walk Through The Forest

HDU 1142 A Walk Through The Forest

Problem Description A Walk Through the Forest Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5891    Accepted Submission(s): 2168 Problem Description Jimmy experiences a lot of stress at work these days, especially since his accident made working difficult. To relax after a hard day, he likes to walk home. To make things even nicer, his office is on one side of a forest, and his house is on the other. A nice walk through the forest, seeing the…

Read More Read More

POJ 1300 Door Man 欧拉路&字符串处理TAT

POJ 1300 Door Man 欧拉路&字符串处理TAT

Door Man Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 2140 Accepted: 859 Description You are a butler in a large mansion. This mansion has so many rooms that they are merely referred to by number (room 0, 1, 2, 3, etc…). Your master is a particularly absent-minded lout and continually leaves doors open throughout a particular floor of the house. Over the years, you have mastered the art of traveling in a single path through the sloppy rooms and…

Read More Read More

HDU 1116 Play on words 欧拉路+并查集

HDU 1116 Play on words 欧拉路+并查集

Problem Description Play on Words Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5576    Accepted Submission(s): 1831 Problem Description Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us. There is a large number of magnetic plates on every door. Every plate has one word written on it….

Read More Read More

POJ 1860 Currency Exchange

POJ 1860 Currency Exchange

Currency Exchange Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 20346 Accepted: 7298 Description Several currency exchange points are working in our city. Let us suppose that each point specializes in two particular currencies and performs exchange operations only with these currencies. There can be several points specializing in the same pair of currencies. Each point has its own exchange rates, exchange rate of A to B is the quantity of B you get for 1A. Also each exchange point…

Read More Read More

单源最短路分析及算法实现

单源最短路分析及算法实现

最短路径的理解性解释:Va 到 Vb 的最短路的意义是 在一个带权图中,从节点Va到节点Vb的权值总和最小的路径 就是Va 到 Vb的最短路,这个权值可以是距离 时间 等各种量 理解最短路径首先要理解什么是最优子结构  最优子结构是在各种动态规划,贪心以及最短路算法中都很关键的一个结构。  最优子结构的意思就是,问题局部的最优解包含在全局的最优解之中,这样才能把问题分成较小的问题先进行处理。 可以通过反证法证明,最短路问题是最优子结构,方法详见 算法导论第三版 P375 在计算最短路之前,还要考虑一个特殊情况,如果在图中存在负权值的边,就可能有一种比较特殊的情况了: 如果 图中存在负权值的边的话但不存在和的权值为负的环,那么 每一个路径的最短距离都可以精确求出,没有问题,不过,如果图中存在和为负权值的环,最短路就没有意义了  因为 总可以通过经过完整的一次环,来得到更小的一个权值 ,理论上 这个最短路径的大小为  -∞ 求最短路的某些算法假设输入的边权值全为非负 如 Dijkstra算法,而还有一些算法只要没有负权值的环就可以 如 Bellman Ford算法 ,如果存在负权值的环的环也可以通过算法报告出来 先试试如何应用这个算法,再继续研究算法的正确性;                             //参考POJ 1860