本科毕业论文图的深度优先遍历及应用.doc

1、 本科毕业论文（设计）论文(设计)题目： 图的深度优先遍历及应用专 业： 计算机科学与技术 班 级： 学 号： 学 生 姓 名： 摘要图是一个最基本、最有表现力的结构，可以用于表示具有各种复杂关系的数据集合，在实际应用中无处不在。虽然问题的状态可以用图来表示，但问题的求解则往往是从状态图中寻找某个状态，或是寻找从一个状态到另一个状态的路径。实现这一求解的过程需要逐步探索与问题有关的各种状态，这即是搜索。这里我们将讨论基于深度优先搜索图的算法，以及该算法的一些相关性质，主要包括：括号定理、后裔区间的嵌套性质和白色路径性质，和由此引出的对边的分类。并给出其应用：一方面是作为基础应用于求无向图中连通

2、分量的个数和求解无向图中通过给定顶点V 的简单回路的算法中；另一方面是对基于 DFS 的图的双向连通性的判断。关键词深度优先遍历；连通分量；简单回路；挂接点AbstractGraphs is the most basic and performance data structure in computer science, it can used for meaning that the data that have various complicated relation gathers, and algorithms for working with them are fundamenta

3、l to the field. Although the status of problem can be meant with Graphs,the solving of problem then usually looks for a certain status from the state graph,or looks for from a path that the status arrives another status.Carry out this various status that the process solving needs to gradually invest

4、igate to have something to do with problem,this is to search. Here we discuss algorithms based on searching a graph using depth-first search, as well as some connected property, including Parenthesis theorem、Nesting of descendants intervals、White-path theorem and Classification of edges derived from

5、 these.Some applications are also given: One is as foundation applied to found the number of connected components in no directed graph; the other hand is to according to the double of DFS graph to connect sexual judgment.Key wordsDFS(Depth First Search); connected components; simple back track; atrp

6、oint 目录绪论11. 深度优先遍历算法的思想及算法12. 深度优先遍历算法的性质22.1.括号性质及其相应性质22.2.边的分类43. 深度优先遍历算法的应用43.1.作为基础应用在其他算法中43.1.1.求无向图中连通分量的个数43.1.2. 求解无向图中通过给定顶点 V 的简单回路43.2. 基于 DFS 的图的双向连通性的判断53.2.1.基本概念53.2.2. 图的双向连通性判断的理论基础53.2.3. 图的双向连通性判断方法及实现63.2.4. 查找挂接点的 DFS 动态树示例74.小结8致谢9参考文献9- 1 -图的深度优先遍历及应用绪论算法分析与设计是计算机科学的灵魂，图论算

7、法是算法中一重要的组成部分，可以用于表示具有各种复杂关系的数据结构，在实际中应用广泛。虽然问题的状态可以用图来表示，但问题的求解则往往是从状态图中寻找某个状态，或是寻找从一个状态到另一个状态的路径。实现这一求解的过程需要逐步探索与问题有关的各种状态，这即是搜索。从一个图的搜索算法中可以发现很多有关于图的结构的信息，因而搜索图的技术又是图论算法领域的核心。深度优先搜索算法是图论最常用的算法之一，是图论中很多其它算法的基础，是图论中的核心算法之一，因此对该算法进行算法分析与设计具有重要的意义。本论题主要研究的内容包括，总结图的深度优先遍历算法发现很多有关于图的结构的信息，以及该算法的一些相关性质。

8、并给出其应用：一方面是作为基础应用于求无向图中连通分量的个数和求解无向图中通过给定顶点 V 的简单回路的算法中；另一方面是基于 DFS 的图的双向连通性的判断。1. 深度优先遍历算法的思想及算法 所谓“ 深度 “是对产生问题的状态结点而言的，“深度优先“是一种控制结点扩展的策略，这种策略是优先扩展深度大的结点，把状态向纵深发展。深度优先搜索也叫做 DFS 法(Depth First Search)。在深度优先搜索中，边是从那些最近发现的但还有未被探测到的边存在的结点v 中探测出来。当 v 的所有边都探测完，搜索将回溯到发现节点 v 的那条边的始节点。这一过程一直进行到我们发现所有初始源结点可达

9、到的结点为止。如果还存在没发现的结点，选其中一个结点作为新的源结点并从该结点开始重复搜索。整个过程反复执行到所有结点都找到为止。在深度优先搜索中为了记录结点的探索状态，我们采用在搜索的过程中对结点染不同的色来描述它们的状态。每个结点初态是白色，搜索过程被发现的时候将其染成灰色，当它的邻接表完全检查完的时候染成黑色。这一技巧保证每个结点在搜索结束时只在一颗深度优先搜索树中，并使这些树分开。除了创建一个深度优先搜索森林外，为了方便，深度优先搜索给每个结点都标上时间邮戳。每个结点v有两个时间邮戳：第一个时间邮戳dv记录了v首次发现（即变灰时）的时间，第二个时间邮戳fv记录了搜索完成（即涂黑的v）的时

10、间。这些时间邮戳对推算深度优先搜索进行情况是很有帮助的，并被使用于很多图论算法中。深度优先搜索的具体思想是： 1、从图的指定顶点 V 出发。 2、先访问顶点 V，并将其标记为灰色。3、依次从 V 的未被访问过的邻接顶点 W 出发进行深度优先搜索（算法需要为 V 的邻接结点假定一种顺序） 。直到图中与 V 连通的所有顶点都访问过。 4、如果图中还有未访问顶点，则选一未访问顶点。由它出发重复上述过程。直到图中所有顶点都被访问为止。 - 2 -其算法为：DFS(G)for each vertex u G-Vu-color = WHITE;time = 0;for each vertex u G-Vi

11、f (u-color = WHITE)DFS_Visit(u);DFS_Visit(u)u-color = GREY;time = time+1;d u = time;for each v u-Adjif (v-color = WHITE)DFS_Visit(v);u-color = BLACK;time = time+1;f u= time; 深度优先搜索过程记录：d u即发现结点u的时间，f u即遍历完成的时间，这些时间邮戳是间于1和2|V|的整数，以后对每个|V|结点有一个发现事件和一个结束事件。对每个结点u，有duadjw; t != NULL; t = t-next)if (pret

12、-v = -1) dfs (G, EDGE(w, t-v);void Graph_search(Graph G) int v, cnt = 0;- 6 -for (v = 0; v V; v+) prev = -1;for (v = 0; v V; v+)if (prev = -1) dfs(G, EDGE(v, v);3.2.3 图的双向连通性判断方法及实现3.2.3.1 判断方法因为双向连通图是不含挂接点的图，因此判断一个图是否为双向连通图这一问题便转化为求一个图中是否存在挂接点。只要能从图中找出挂接点，则此图一定不是双向连通图。在DFS动态树中，有两类挂接点，它们的特性分别如下:（1）

13、若DFS 动态树的根结点为挂接点当且仅当其至少有两个子女。证明：因为图中不存在连接不同子树中结点的边，因此，若删去根结点，DFS 树便变成DFS 森林，所以若DFS 动态树的根有两棵或两棵以上的子树，则根结点必为挂接点。（2） 若DFS 动态树中某个非叶子结点v，其某棵子树的根和子树中的其它结点均没有指向v 的祖先的后向边，则结点v 为挂接点。证明：因为，若删去v，则其子树和图的其它部分被分割开来，所以对DFS 动态树中某个非叶子结点v，其某棵子树的根和子树中的其它结点均没有指向v 的祖先的后向边，则结点v 为挂接点。为了找出挂接点的集合，在图G 上执行深度优先搜索遍历，在遍历的过程中，对每个

14、顶点v 保持两个编号 : 前序编号prev和最低前序编号lowv，prev只是深度优先搜索算法中的cnt，每次调用深度优先搜索算法时，cnt加1，lowv初始化为prev，但在后来的遍历过程中可以改变，对于每一个访问的顶点v，其最低前序编号lowv计算如下:prevlowv=Min loww，w是顶点v在生成树上的孩子顶点， （v，w）Eprek，k顶点v生成树上由后向边连接的祖先顶点， （v，k）E若对于某个顶点v，存在孩子顶点w且lowwprev，则该顶点v必为挂接点。因为，当w是v的孩子顶点时，loww prev，表明以w为根的子树和子树中的顶点均无指向v的祖先的后向边。3.2.3.2 方法实现利用递归函数Dfs_articul 求图中的关节点。它使用一个计数器bnct和一个挂接点数组ac，low数组跟踪每一个顶点的最低前序编号。static int cnt, acnt, root, rootdegree, premaxV,lowmaxV,acmaxV;void Graph_articul(Graph G) int v; link t;for (v = 0; v V; v+) prev = -1;cnt=0; / 图的顶点计数器acnt=0; / 图的挂接点计数器rootdegree=0; / 根顶点的度Dfs_articul(G, EDGE(root, root);