网站用社交图标做链接侵权吗,wordpress显示未登录,深圳网站建设厂家哪家好,全网营销是什么意思https://blog.csdn.net/jeryjeryjery/article/details/52829142?locationNum4fps1 以防链接失效#xff0c;特此转载此博#xff0c;如有侵权请见谅 在有向图G中#xff0c;如果两个顶点间至少存在一条路径#xff0c;称两个顶点强连通(strongly connected)。如果有向…https://blog.csdn.net/jeryjeryjery/article/details/52829142?locationNum4fps1 以防链接失效特此转载此博如有侵权请见谅 在有向图G中如果两个顶点间至少存在一条路径称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通称G是一个强连通图。非强连通图有向图的极大强连通子图称为强连通分量(strongly connected components)。如下图中强连通分量有{1,2,3,4}{5}{6} Tarjan算法是基于对图深度优先搜索的算法每个强连通分量为搜索树中的一棵子树。搜索时把当前搜索树中未处理的节点加入一个堆栈回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。Tarjan算法有点类似于基于后序的深度遍历搜索和并查集的组合充分利用回溯来解决问题。在Tarjan算法中为每个节点i维护了以下几个变量DFN[i]深度优先搜索遍历时节点i被搜索的次序。low[i]节点i能够回溯到的最早位于栈中的节点。flag[i]标记几点i是否在栈中。Tarjan算法的运行过程1.首先就是按照深度优先搜索算法搜索的次序对图中所有的节点进行搜索。2.在搜索过程中对于任意节点u和与其相连的节点v根据节点v是否在栈中来进行不同的操作*节点v不在栈中即节点v还没有被访问过则继续对v进行深度搜索。*节点v已经在栈中即已经被访问过则判断节点v的DFN值和节点u的low值的大小来更新节点u的low值。如果节点v的 DFN值要小于节点u的low值根据low值的定义能够回溯到的最早的已经在栈中的节点我们需要用DFN值来更新u 的low值。3.在回溯过程中对于任意节点u用其子节点v(其实不能算是子节点只是在深度遍历的过程中v是在u之后紧挨着u的节点)的 low值来更新节点u的low值。因为节点v能够回溯到的已经在栈中的节点节点u也一定能够回溯到。因为存在从u到v的直接路径所以v能够到的节点u也一定能够到。 4.对于一个连通图我们很容易想到在该连通图中有且仅有一个节点u的DFN值和low值相等。该节点一定是在深度遍历的过程中该连通图中第一个被访问过的节点因为它的DFN值和low值最小不会被该连通图中的其他节点所影响。 下面我们证明为什么仅有一个节点的DFN和low值相等。假设有两个节点的DFN值和low值相等由于这两个节点的DFN值一定不相同 DFN值的定义就是深度遍历时被访问的先后次序所以两个的low值也绝对不相等。由于位于同一个连通图中所以两个节点必定相互可达那么两者的low值一定会被另外一个所影响要看谁的low值更小所以不可能存在两对DFN值和low值相等的节点。 所以我们在回溯的过程中就能够通过判断节点的low值和DFN值是否相等来判断是否已经找到一个子连通图。由于该连通图中的DFN值和low值相等的节点是该连通图中第一个被访问到的节点又根据栈的特性(先压入 栈的节点在栈的更里面)则该节点在最里面。所以能够通过不停的弹栈直到弹出该DFN值和low值相同的节点来弹出该连通图中所有的节点。 Tarjan算法的C实现代码如下可以配合上面的图加以理解 [cpp] view plaincopy #includeiostream using namespace std; int DFN[105]; //记录在做dfs时节点的搜索次序 int low[105]; //记录节点能够找到的最先访问的祖先的记号 int count1; //标记访问次序时间戳 int stack[105]; //压入栈中 int top-1; int flag[105]; //标记节点是否已经在栈中 int number0; int j; int matrix[105][105]{{0,1,1,0,0,0},{0,0,0,1,0,0},{0,0,0,1,1,0},{1,0,0,0,0,1},{0,0,0,0,0,1},{0,0,0,0,0,0}}; int length; //图的长度 void tarjan(int u){ DFN[u]low[u]count; //初始化两个值自己为能找到的最先访问的祖先 stack[top]u; flag[u]1; //标记为已经在栈中 for(int v0;vlength;v){ if(matrix[u][v]){ if(!DFN[v]){ //如果点i没有被访问过 tarjan(v); //递归访问 if(low[v]low[u]) low[u]low[v]; //更新能找的到祖先 } else{ //如果访问过了并且该点的DFN更小则 if(DFN[v]low[u]flag[v]) //flag[v]这个判断条件很重要这样可以避免已经确定在其他联通图的v,因为u到v的单向边而影响到u的low low[u]DFN[v]; //也就是已经确定了的联通图要剔除掉剔除的办法就是判断其还在栈中因为已经确定了的连通图的点 } //flag在下面的do while中已经设为0了(即已经从栈中剔除了) } } //往后回溯的时候如果发现DFN和low相同的节点就可以把这个节点之后的节点全部弹栈构成连通图 if(DFN[u]low[u]){ number; //记录连通图的数量 do{ jstack[top--]; //依次取出直到u coutj ; flag[j]0; //设置为不在栈中 }while(j!u); coutendl; } } int main(){ memset(DFN,0,sizeof(DFN)); //数据的初始化 memset(low,0,sizeof(low)); memset(flag,0,sizeof(flag)); length6; tarjan(0); coutendl; for(int i0;i6;i){ coutDFN[i]:DFN[i] low[i]:low[i]endl; } return 0; } 转载于:https://www.cnblogs.com/cglongge/p/8722202.html
