网站的关键词库怎么做的那么多,东莞网站开发哪里找,三端互通传奇手游找服网站,东莞微网站建设公司【0】README
0.1#xff09; 本文总结于 数据结构与算法分析#xff0c; 源代码均为原创#xff0c; 旨在 理解 “DFS应用——查找强分支” 的idea 并用源代码加以实现 #xff1b; 【1】查找强分支
1.1#xff09;如何检测一个图是否是强连通的#xff1a; 通过执行两…【0】README
0.1 本文总结于 数据结构与算法分析 源代码均为原创 旨在 理解 “DFS应用——查找强分支” 的idea 并用源代码加以实现 【1】查找强分支
1.1如何检测一个图是否是强连通的 通过执行两次DFS 我们可以检测一个有向图是否是强连通的 如果它不是强连通的那么我们实际上可以得到顶点的一个子集 它们到其自身是强连通的 1.2首先 在输入的图G上执行一次 DFS。 通过对深度优先生成森林的后序遍历将G的顶点编号 然后再把G 的所有边反向形成 Gr**如何构建 Gr** 1.3上述算法通过对 Gr 执行一次深度优先搜索而完成 总是在编号最高的顶点开始一次新的DFS。于是我们在顶点G 开始对 Gr 的DFS G的编号为10。 1.4但该顶点不通向任何顶点 因此下一次搜索在H 点开始以下查找强分支的过程仅仅是一个可能的case仅举例而已。 这次调用访问 I 和 J。 下一次调用在B点开始并访问 A、C 和 F。 此后的调用时 DFSD以及最终调用DFSE。 1.5结果得到的深度优先生成森林如下图所示 1.6对深度优先生成森林中的分析 在该深度优先生成森林中的每棵树形成一个强连通分支。 对于我们的例子 这些强连通分支为 {G} {HIJ} {BACF}{D} 和 {E} 1.7为了理解上述算法为什么成立
1.7.1首先注意到 如果两个顶点v 和 w 都在同一个强连通分支中那么在原图G中就存在从 v到w 和从w到v的路径因此 在Gr中也存在。1.7.2现在如果两个顶点v 和 w 不在Gr的同一个深度优先生成树中那么显然它们也不可能在同一个强连通分支中 【2】source code printing results
2.1download source code https://github.com/pacosonTang/dataStructure-algorithmAnalysis/tree/master/chapter9/p249_dfs_strong_component 2.2source code at a glancefor complete code , please click the given link above
// finding the strong component from the reverse graph and strongComponent derives from dfs
void strongComponent(Vertex vertex, int depth)
{int i;AdjTable temp;Vertex adjVertex; //printf(\n\t visited[%c] 1 , flag[vertex]);visited[vertex] 1; // update visited status of vertexvertexIndex[vertex] counter; // number the vertex with countertemp reverseAdj[vertex]; while(temp-next){printf( );adjVertex temp-next-vertex; if(visited[adjVertex]) // judge whether the adjVertes was visited before {if(vertexIndex[vertex] vertexIndex[adjVertex] parent[vertex] ! adjVertex) {//parent[adjVertex] vertex; // building back side, attention of condition of building back side above// just for printing effectfor(i 0; i depth; i) printf( );printf(v[%c]-v[%c] (backside) \n, flag[vertex], flag[adjVertex]);}}else{parent[adjVertex] vertex;// just for printing effectfor(i 0; i depth; i) printf( );printf(v[%c]-v[%c] (building edge)\n, flag[vertex], flag[adjVertex]); strongComponent(adjVertex, depth1);} temp temp-next; }
}
2.3printing results
