文件列表:

deep first searching\src\df (7529, 2011-05-23)
deep first searching\src\dfs.c (4334, 2011-05-23)
deep first searching\src\dfs.h (740, 2011-05-23)
deep first searching\src\input (35, 2011-05-23)
deep first searching\src\output (51, 2011-05-23)
deep first searching\源程序\Applications of Depth-First Traversal.cpp (1260, 2011-05-23)
deep first searching\源程序\dfs.pdf (102796, 2011-05-23)
deep first searching\源程序\DFS拓扑排序.h (2952, 2011-05-23)
deep first searching\源程序\两种方法求有向图的拓扑排序.h (573, 2011-05-23)
deep first searching\源程序\判定图的半连通性.h (4308, 2011-05-23)
deep first searching\源程序\判断图的单连通.h (1622, 2011-05-23)
deep first searching\源程序\判断图的双连通.h (1700, 2011-05-23)
deep first searching\源程序\无向图的连通性.h (862, 2011-05-23)
deep first searching\源程序\有向图强连通分量.h (1705, 2011-05-23)
deep first searching\源程序\有向图边分类.h (2049, 2011-05-23)
deep first searching\源程序\点消除拓扑排序.h (2606, 2011-05-23)
deep first searching\src (0, 2011-05-23)
deep first searching\源程序 (0, 2011-05-23)
deep first searching (0, 2012-02-26)

1. A tree edge is an edge in a DFS-tree. 2. A back edge connects a vertex to an ancestor in a DFS-tree. Note that a self-loop is a back edge. 3. A forward edge is a non-tree edge that connects a vertex to a descendent in a DFS-tree. 4. A cross edge is any other edge in graph G. It connects vertices in two different DFS-tree or two vertices in the same DFS-tree neither of which is the ancestor of the other. Lemma 1 An Edge (u, v) is a back edge if and only if d[v] < d[u] < f[u] < f[v]. Proof (=> direction) From the definition of a back edge, it connects vertex u to an ancestor vertex v in a DFS-tree. Hence, vertex u is a descendent of vertex v. Corollary 22.8 in the CLRS (or see above) states that vertex u is a proper descendent of vertex v if and only if d[v] < d[u] < f[u] < f[v]. Hence proved forward direction. (<= direction) Again by the Corollary 22.8 (CLRS), vertex u is a proper descendent of vertex v. Hence if an edge (u, v) exists from u to v then it is an edge connecting a descendent vertex u to its ancestor vertex v. Hence, it is a back edge. Hence proved backward direction. Conclusion: Immediate from both directions. Lemma 2 An edge (u, v) is a cross edge if and only if d[v] < f[v] < d[u] < f[v]. Proof First take => direction. Observation 1 For an edge (u, v), d[u] < f[u] and d[v] < f[v] since for any vertex has to be discovered before we can finish exploring it. Observation 2 From the definition of a cross edge it is an edge which is not a tree edge, forward edge or a backward edge. This implies that none of the relationships for forward edge {d[u] < d[v] < f[v] < f[u]} or back edge {d[v] < d[u] < f[u] < f[v]} can hold for a cross edge. From the above two observations we conclude that the only two possibilities are: 1. d[u] < f[u] < d[v] < f[v] 2. d[v] < f[v] < d[u] < f[u] When the cross edge (u, v) is discovered we must be at vertex u and vertex v must be black. The reason is that if v was white then edge (u, v) would be a tree edge and if v was gray edge (u, v) would be a back edge. Therefore, d[v] < d[u] and hence possibility (2) holds true.

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：