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

本科毕业论文（设计）论文(设计)题目： 图的深度优先遍历及应用 专 业： 计算机科学与技术 班 级： 学 号： 学 生 姓 名： 摘要图是一个最基本、最有表现力的结构，可以用于表示具有各种复杂关系的数据集合，在实际应用中无处不在。虽然问题的状态可以用图来表示，但问题的求解则往往是从状态图中寻找某个状态，或是寻找从一个状态到另一个状态的路径。实现这一求解的过程需要逐步探索与问题有关的各种状态，这即是搜索。这里我们将讨论基于深度优先搜索图的算法，以及该算法的一些相关性质，主要包括：括号定理、后裔区间的嵌套性质和白色路径性质，和由此引出的对边的分类。并给出其应用：一方面是作为基础应用于求无向图中连通分量的个数和求解无向图中通过给定顶点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 fundamental 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 investigate 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 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; atrpoint 目录 绪论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图的深度优先遍历及应用绪论算法分析与设计是计算机科学的灵魂，图论算法是算法中一重要的组成部分，可以用于表示具有各种复杂关系的数据结构，在实际中应用广泛。虽然问题的状态可以用图来表示，但问题的求解则往往是从状态图中寻找某个状态，或是寻找从一个状态到另一个状态的路径。实现这一求解的过程需要逐步探索与问题有关的各种状态，这即是搜索。从一个图的搜索算法中可以发现很多有关于图的结构的信息，因而搜索图的技术又是图论算法领域的核心。深度优先搜索算法是图论最常用的算法之一，是图论中很多其它算法的基础，是图论中的核心算法之一，因此对该算法进行算法分析与设计具有重要的意义。本论题主要研究的内容包括，总结图的深度优先遍历算法发现很多有关于图的结构的信息，以及该算法的一些相关性质。并给出其应用：一方面是作为基础应用于求无向图中连通分量的个数和求解无向图中通过给定顶点V的简单回路的算法中；另一方面是基于DFS 的图的双向连通性的判断。1. 深度优先遍历算法的思想及算法 所谓深度是对产生问题的状态结点而言的，深度优先是一种控制结点扩展的策略，这种策略是优先扩展深度大的结点，把状态向纵深发展。深度优先搜索也叫做DFS法(Depth First Search)。在深度优先搜索中，边是从那些最近发现的但还有未被探测到的边存在的结点v中探测出来。当v的所有边都探测完，搜索将回溯到发现节点v的那条边的始节点。这一过程一直进行到我们发现所有初始源结点可达到的结点为止。如果还存在没发现的结点，选其中一个结点作为新的源结点并从该结点开始重复搜索。整个过程反复执行到所有结点都找到为止。在深度优先搜索中为了记录结点的探索状态，我们采用在搜索的过程中对结点染不同的色来描述它们的状态。每个结点初态是白色，搜索过程被发现的时候将其染成灰色，当它的邻接表完全检查完的时候染成黑色。这一技巧保证每个结点在搜索结束时只在一颗深度优先搜索树中，并使这些树分开。除了创建一个深度优先搜索森林外，为了方便，深度优先搜索给每个结点都标上时间邮戳。每个结点v有两个时间邮戳：第一个时间邮戳dv记录了v首次发现（即变灰时）的时间，第二个时间邮戳fv记录了搜索完成（即涂黑的v）的时间。这些时间邮戳对推算深度优先搜索进行情况是很有帮助的，并被使用于很多图论算法中。深度优先搜索的具体思想是： 1、从图的指定顶点V出发。 2、先访问顶点V，并将其标记为灰色。3、依次从V的未被访问过的邻接顶点W出发进行深度优先搜索（算法需要为V的邻接结点假定一种顺序）。直到图中与V连通的所有顶点都访问过。 4、如果图中还有未访问顶点，则选一未访问顶点。由它出发重复上述过程。直到图中所有顶点都被访问为止。 其算法为：DFS(G) for each vertex u G-V u-color = WHITE; time = 0; for each vertex u G-V if (u-color = WHITE) DFS_Visit(u); DFS_Visit(u) u-color = GREY; time = time+1; d u = time; for each v u-Adj if (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，有dufu。结点u在时间du前是白色，时间du到fu内是灰色，此后是黑色。算法时间复杂度分析：DFS(G)中循环所占用的时间为O(V)，但这并不包括调用DFS_Visit过程语句所耗费的时间。事实上对V中的每个顶点DFS_Visit仅被调用一次，因为DFS_Visit仅适用于白色顶点，并在执行完后将其涂成灰色。而在DFS_Visit执行的过程只中所耗费的时间为O(E)，所以算法的运行时间为O(V+E)。2.深度优先遍历算法的性质2.1括号性质及其相应性质依据深度优先搜索可以获得有关图的结构的大量信息。也许深度优先搜索的最基本的特征是它的先辈子图G，形成一个由树组成的森林，这是因为深度优先树的结构准确反映了DFS_Visit中递归调用的结构的缘故，即u=v当且仅当在搜索u的邻接表过程中调用了过程DFS_Visit(v)。另外，结点u是深度优先搜索森林中结点v 的子孙当且仅当v在u是灰色时被发现。 深度优先搜索另一个重要的性质是发现和结束时间有括号结构。如果我们把发现结点u表示为“(u”，把结束表示为“u)”，那么发现和结束的过程，从括号的后裔区间的嵌套性质上讲，就得到一个良好的表达。例如，图示2.1(a)图深度优先搜索对应了图2.1(b)中的括号表示。另一个确定括号结构条件的是以下给出的定理 。 （1） 括号性质 在对有向图或无向图G=(V,E)的任何深度优先搜索中，对于图中任意两结点u和v，下述三个条件中有且仅有一条成立：区间du，fu和区间dv，fv是完全分离的；区间du，fu完全包含于区间dv，fv中且在深度优先树中u是v的后裔； 区间dv，fv完全包含于区间du，fu中且在深度优先树中v是u的后裔。 （2）后裔区间的嵌套性质 在某一有向（或无向）图中的深度优先搜索森林中，结点v是结点u的子孙当且仅当dudvfvfu 。（3）白色路径性质 在一有向（或无向）图G=（V，E）的深度优先搜索森林中，结点v是结点u的子孙当且仅当在搜索到u的时间du，结点u可以顺着一条包含所有白色结点的路径到达v。2.2边的分类 深度优先搜索另一个有趣的性质是，可以通过搜索对输入图G=（V，E）的边进行归类。这种归类可以发现图的很多重要信息。根据在图G上进行深度优先搜索所产生的深度优先森林G，我们可以把图的边分为四种类型。1、树边，是深度优先森林G中的边，如果结点v是在探寻边(u，v)时第一次被发现，那么边(u，v)就是一个树边。 2、反向边，是深度优先树中连结结点u到它的祖先v的那些边，环也被认为是反向边。 3、正向边，是指深度优先树中连接顶点u到它的后裔的非树边的边。 4、交叉边，是指所有其他类型的边，它们可以连结同一棵深度优先树中的两个结点，只要一结点不是另一结点的祖先，也可以连结分属两棵深度优先树的结点。 DFS算法修改成当它对边计数时完成对边的分类。关键思想是每条边（u，v）当首次被探测到（除前向边和交叉边不用区分）时，可以由结点v的颜色决定： 1、白色树边 2、灰色反向边 3、黑色前向或交叉边 由以上规则我们可以发现在深度优先搜索无向图时不会出现正向边和交叉边。即可得到定理：定理1在对无向图G进行深度优先搜索的过程中，G的每条边要么是树边要么是反向边。证明:设(u，v)为G的任意一边，不失一般性，假定duadjw; t != NULL; t = t-next)if (pret-v = -1) dfs (G, EDGE(w, t-v);void Graph_search(Graph G) int v, cnt = 0;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） 若DFS 动态树的根结点为挂接点当且仅当其至少有两个子女。证明：因为图中不存在连接不同子树中结点的边，因此，若删去根结点，DFS 树便变成DFS 森林，所以若DFS 动态树的根有两棵或两棵以上的子树，则根结点必为挂接点。（2） 若DFS 动态树中某个非叶子结点v，其某棵子树的根和子树中的其它结点均没有指向v 的祖先的后向边，则结点v 为挂接点。证明：因为，若删去v，则其子树和图的其它部分被分割开来，所以对DFS 动态树中某个非叶子结点v，其某棵子树的根和子树中的其它结点均没有指向v 的祖先的后向边，则结点v 为挂接点。为了找出挂接点的集合，在图G 上执行深度优先搜索遍历，在遍历的过程中，对每个顶点v 保持两个编号: 前序编号prev和最低前序编号lowv，prev只是深度优先搜索算法中的cnt，每次调用深度优先搜索算法时，cnt加1，lowv初始化为prev，但在后来的遍历过程中可以改变，对于每一个访问的顶点v，其最低前序编号lowv计算如下: prev lowv=Min loww，w是顶点v在生成树上的孩子顶点，（v，w）E prek，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);void Dfs_articul(Graph G, Edge e) link t;int w, v = e.w;atrpoint=FALSE;/ atrpoint 标记当前顶点v 是否为挂接点prev = cnt+; lowv = prev;for (t = G-adjv; t != NULL; t = t-next)if (prew = t-v = -1) /树边 Dfs_articul(G, EDGE(v, w);if(v=root) /处理根顶点 rootdegree+;if(rootdegree=2) atrpoint=TRUE;else / 处理非根顶点 if (lowv loww) lowv = loww;if (loww = prev) atrpoint=TRUE;else if (v != e.v) /后向边if (lowv prew) lowv = prew;if (atrpoint=TRUE) acnt+; acacnt=v;3.2.3.3 复杂度分析设有V个顶点、E条边的无向图，对于邻接矩阵表达方式，查找图中挂接点的时间复杂度为O(V2)。对于邻接表表达方式，查找图中挂接点的时间复杂度为O(V+E)。3.2.4 查找挂接点的D