手机编程网站,搭建网站要多久,直接推广和间接推广区别,宣城网站seo【0】README 0.1#xff09; 本文总结于 数据结构与算法分析#xff0c; 源代码均为原创#xff0c; 旨在 理解 “DFS应用——遍历有向图判断有向图是否有圈” 的idea 并用源代码加以实现 #xff1b;0.2#xff09; 判断有向图是否有圈的rule—— 一个有向图是无圈图当且… 【0】README 0.1 本文总结于 数据结构与算法分析 源代码均为原创 旨在 理解 “DFS应用——遍历有向图判断有向图是否有圈” 的idea 并用源代码加以实现 0.2 判断有向图是否有圈的rule—— 一个有向图是无圈图当且仅当它没有背向边背向边定义参见 http://blog.csdn.net/pacosonswjtu/article/details/49967255 0.3 代码最后还添加了打印dfs遍历路径所产生的集合 对的dfs 就应该这么玩Bingo 【1】有向图相关 1.1对有向图进行DFS的idea利用与无向图相同的思路 也可以通过深度优先搜索以线性时间遍历有向图。如果图不是强连通的那么从某个节点开始的DFS可能访问不了所有的节点。在这种情况下 我们在某个未作标记的节点处开始反复执行DFS 直到所有节点都被访问到1.2基于以上描述 我们看个荔枝这只是一种可能的case step1从顶点B 任意开始深度优先搜索 访问顶点B, C, A, D, Estep2从顶点 F 任意开始DFS 访问顶点 Fstep3从顶点 H 任意开始DFS 访问顶点 H, J, Istep4从顶点 G 任意开始DFS 访问顶点 G1.3对于以上的DFS过程 对应的搜索优先搜索树如下图所示对上图的分析Analysis A1深度优先生成森林中虚线箭头是一些v, w边 其中的w 在考察时已经做了标记A2我们看到存在三种类型的边并不通向新顶点 A2.1背向边如AB 和 IHA2.2前向边如CD 和 CE 它们从树的一个节点通向一个后裔A2.3交叉边如FC和GF 它们把不直接相关的两个树节点连接起来A3深度优先搜索森林一般通过吧一些子节点和一些新的树从左到右添加到森林中形成。 在以这种方式构成的有向图的深度优先搜索中交叉边总是从右到左进行的1.4深度优先搜索DFS的一个用途是 检测一个有向图是否是无圈图 4.1 法则如下 一个有向图是无圈图当且仅当它没有背向边上面的图有背向边 因此它不是无圈图4.2拓扑排序也可以用来确定一个图是否是无圈图。进行拓扑排序的另一种方法是通过深度优先生成森林的后序遍历给顶点指定拓扑编号N N-1 ..., 1; 只要图是无圈的这种排序就是一致的【2】source code printing results此处的dfs是对原始dfs修改而成的与原始的dfs不同但idea一样 2.1download source code https://github.com/pacosonTang/dataStructure-algorithmAnalysis/tree/master/chapter9/p248_dfs_directed_graph2.2source code at a glancefor complete code , please click the given link above void dfs(Vertex vertex, int depth)
{int i;int visitFlag;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 adj[vertex]; visitFlag 0; while(temp-next){ 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]);} }//if(!visited[adjVertex])else{if(vertex start)visitFlag 1;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]);dfs(adjVertex, depth1);}if(vertex start visitFlag) //conducingt dfs for only one adjoining vertex in the given graphbreak; temp temp-next; }
} 2.3printing results第二张图是对第一张图的补充我最后添加了 dfsPathSet 方法打印出上述dfs遍历路径所产生的集合 转载于:https://www.cnblogs.com/pacoson/p/4990616.html
