本文目录一览

1，tarjan算法 为什么low

tarjan主要时间是用在RMQ的构建上，即遍历树，然后构造遍历数组，构造RMQ序列。 这里的时间复杂度大约是O(2*n*log(2*n))。 而对于一个询问，处理速度大约是O(1)，即从RMQ序列中查询相应节点的位置，以及对比操作。
没看懂什么意思？

tarjan算法 为什么low

2，求最近公共祖先的tarjan算法pascal标程

首先从顶点a出发，沿父指针将a至根的路径上的所有顶点设访问标志。然后从b顶点出发，沿父指针追溯到第1个已访问的顶点b，该顶点即为a和b的最近公共祖先。 var n,rt,a,b,i:integer; l,r,pt:array[0..max]of integer; vt:array[1..max]of boolean; readln(f,n,rt); for i:=1 to n do begin readln(l[i],r[i]); if i=rt then pt[rt]:=0 else pt[l[i]]:=i; pt[r[i]]:=i end; readln(a,b); while a*b<>0 do begin fillchar(vt,sizeof(vt),0); repeat vt[a]:=true;a:=pt[a] until a=0; while not vt[b] do b:=pt[b]; writeln(b);readln(a,b); End;

求最近公共祖先的tarjan算法pascal标程

3，最近公共祖先的算法

利用并查集优越的时空复杂度，我们可以实现LCA问题的O(n+Q)算法，这里Q表示询问的次数。Tarjan算法基于深度优先搜索的框架，对于新搜索到 的一个结点，首先创建由这个结点构成的集合，再对当前结点的每一个子树进行搜索，每搜索完一棵子树，则可确定子树内的LCA询问都已解决。其他的LCA询 问的结果必然在这个子树之外，这时把子树所形成的集合与当前结点的集合合并，并将当前结点设为这个集合的祖先。之后继续搜索下一棵子树，直到当前结点的所 有子树搜索完。这时把当前结点也设为已被检查过的，同时可以处理有关当前结点的LCA询问，如果有一个从当前结点到结点v的询问，且v已被检查过，则由于 进行的是深度优先搜索，当前结点与v的最近公共祖先一定还没有被检查，而这个最近公共祖先的包涵v的子树一定已经搜索过了，那么这个最近公共祖先一定是v 所在集合的祖先。下面给出这个算法的伪代码描述： LCA(u)d[i] 表示 i节点的深度, p[i,j] 表示 i 的 2^j 倍祖先那么就有一个递推式子 p[i,j]=p[p[i,j-1],j-1]这样子一个O(NlogN)的预处理求出每个节点的 2^k 的祖先然后对于每一个询问的点对a, b的最近公共祖先就是：先判断是否 d[a] > d[b] ,如果是的话就交换一下(保证 a 的深度小于 b 方便下面的操作)然后把b 调到与a 同深度, 同深度以后再把a, b 同时往上调(dec(j)) 调到有一个最小的j 满足p[a,j]!=p[b,j] (a b 是在不断更新的), 最后再把 a, b 往上调 (a=p[a,0], b=p[b,0]) 一个一个向上调直到a = b, 这时 a or b 就是他们的最近公共祖先

最近公共祖先的算法

4，强连通分量的Tarjan算法思路

这个算法思路不难理解，由开篇第一句话可知，任何一个强连通分量，必定是对原图的深度优先搜索树的子树。那么其实，我们只要确定每个强连通分量的子树的根，然后根据这些根从树的最低层开始，一个一个的拿出强连通分量即可。那么剩下的问题就只剩下如何确定强连通分量的根和如何从最低层开始拿出强连通分量了。那么如何确定强连通分量的根，在这里我们维护两个数组，一个是indx[1..n]，一个是mlik[1..n]，其中indx[i]表示顶点i开始访问时间，mlik[i]为与顶点i邻接的顶点未删除顶点j的mlik[j]和mlik[i]的最小值(mlik[i]初始化为indx[i])。这样，在一次深搜的回溯过程中，如果发现mlik[i]==indx[i]那么，当前顶点就是一个强连通分量的根，为什么呢？因为如果它不是强连通分量的根，那么它一定是属于另一个强连通分量，而且它的根是当前顶点的祖宗，那么存在包含当前顶点的到其祖宗的回路，可知mlik[i]一定被更改为一个比indx[i]更小的值。至于如何拿出强连通分量，这个其实很简单，如果当前节点为一个强连通分量的根，那么它的强连通分量一定是以该根为根节点的(剩下节点)子树。在深度优先遍历的时候维护一个堆栈，每次访问一个新节点，就压入堆栈。现 在知道如何拿出了强连通分量了吧？是的，因为当前节点是这个强连通分量中最先被压入堆栈的，那么在当前节点以后压入堆栈的并且仍在堆栈中的节点都属于这个强连通分量。当然有人会问真的吗？假设一个节点在当前节点压入堆栈以后压入并且还存在，同时它不属于该强连通分量，那么它一定属于另一个强连通分量，但当前节点是它的根的祖宗，那么这个强连通分量应该在此之前已经被拿出。现 在没有疑问了吧，那么算法介绍就完了。

5，具有7个定点的无向图至少应有几条边才能确保是一个连通图

至少有n条边，正好可以组成一个环。无向连通图指的是图中的每个顶点都有边与其相连，且图中没有断处，即对无向连通图进行遍历时，仅需要从图中的一个顶点出发。进行深度优先或广度优先搜索，便可以访问到图中所有的顶点。无向连通图构成的条件是：边数=顶点数-1。连通分量的提出是以"整个无向图不是连通图"为前提的，因为如果无向图是连通图，则其无法分解出多个最大连通子图，因为图中所有的顶点之间都是连通的。扩展资料：无向图到连通图的tarjan算法：如果两个顶点可以相互通达，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。下图中，子图Tarjan算法是用来求有向图的强连通分量的。求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法。Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。参考资料来源：百度百科—连通图百度百科—无向图百度百科—tarjan算法
强连通图必须从任何一点出发都可以回到原处,每个节点至少要一条出路(单节点除外)至少有n条边,正好可以组成一个环。
具有n个顶点的无向图，至少应有多少条边才能确保是一个 连通图? 若采用邻接矩阵表示，则该矩阵的大小是多少?

6，C Tarjan到底干嘛的怎么写

Tarjan算法是用来求有向图的强连通分量的。这是c++代码，　　#define M 50//题目中可能的最大点数　　intSTACK[M],top=0;//Tarjan算法中的栈　　boolInStack[M];//检查是否在栈中　　intDFN[M];//深度优先搜索访问次序　　intLow[M];//能追溯到的最早的次序　　intComponentNumber=0;//有向图强连通分量个数　　intIndex=0;//索引号　　vectorEdge[M];//邻接表表示 　　vectorComponent[M];//获得强连通分量结果 　　intInComponent[M];//记录每个点在第几号强连通分量里 　　intComponentDegree[M];//记录每个强连通分量的度 　　voidTarjan(inti){intj; 　　DFN[i]=Low[i]=Index++; 　　InStack[i]=true; 　　STACK[++top]=i; 　　for(inte=0;e 　　{ 　　　j=Edge[i][e]; 　　　if(DFN[j]==-1) 　　　{ 　　　　Tarjan(j); 　　 Low[i]=min(Low[i],Low[j]); 　　　} 　　　else if(InStack[j]) 　　　　Low[i]=min(Low[i],Low[j]); 　　} 　　if(DFN[i]==Low[i]) 　　{ 　　　　ComponentNumber++; 　　　　do{ 　　　　j=STACK[top--]; 　　　　InStack[j]=false; 　　　　Component[ComponentNumber].push_back(j); 　　　　InComponent[j]=ComponentNumber; 　　　　}while(j!=i); 　　}
在c语言中return 表示从被调函数返回到主调函数继续执行，返回时可附带一个返回值，由return后面的参数指定。　　因此，在c语言中一般出现return语句，即改变程序执行流程到母函数中，因此无论是在if语句还是while语句，还是其它的什么语句，return始终是返回母函数的调用，不需要细分什么情况。

文章TAG：tarjan算法  tarjan算法  为什么low  
下一篇
展开更多