关于遍历算法的研究与应用的论文

Pick toGraph is a kind of complex data structure, the relationship between the nodes can be arbitrarily, between any two elements in May, and in many applications are used widely. The graph theory is the study of the knowledge map is a subject, a powerful tool for many practical problems, and realize the traversal graph theory is one of the basic questions, this is also the paper to paper briefly introduces the development course of graph theory and application, Then it analyses the graph depth-first and breadth-first traversing algorithm, On this basis, using C language in to realize the development environment of Tc graph traversing algorithm of two kinds of main contents include: 1) from the keyboard input figure of vertex and edge, or a graph randomly generated, 2) using a 2d array to store the adjacency matrix, and the figure shows the adjacency matrix in computer screen, 3) using depth-first traversing algorithm or breadth-first traversing algorithm corresponding vertex traverse sequence, then use graphics functions traverse graphical : graph, Depth-first traversal, Breadth-first traversal, The adjacency matrix,

Abstract the chart is one kind of complex construction of data, between its node's relations may be random, in the chart between the random two elements possibly is related, thus obtains the widespread application in many application domains. The graph theory is studies the chart related knowledge a knowledge, is solves many actual problem powerful tools, the chart traversal and realizes is one of graph theory basic questions, this is also precisely the question which this article needs to study. this article first briefly introduced the graph theory development process and the application; Then analyzed the chart depth first first traversal the algorithm with the breadth; Based on this, used the C language to realize Figure two kind of traversal algorithm programming in the Win-Tc development environment to realize. mainly realizes the content includes: 1) inputs the chart from the keyboard the apex and side, or produces a chart stochastically, 2) uses the two-dimension array to save the chart the adjacent matrix, and the adjacent matrix demonstration in the computer screen, 3) first traversal using the depth the algorithm or the breadth first traversal the algorithm to extract the corresponding apex traversal order, then the use cartography function carries on the traversal order the presente in figures and diagrams demonstration. key word: Graph theory; The depth first traversal; The breadth first traversal; Adjacent matrix;

树有很多应用，流行的用法之一是包括 UNIX、VAX/VMS 和 DOS 在内的许多常用操作系统中的目录结构。 假设我们有一个根目录 A，A 目录下有一个目录 B，B 目录下有一个目录 C，C 目录下有一个文件 D。此时，文件 D 的全路径名就为 A/B/C/D，其中，每一个 “/” 后的每一个 “/”在树中都表示一条边，这个分级文件系统非常流行，因为它能够使得用户逻辑地组织数据。不仅如此，在不同目录下的两个文件还可以享有相同的名字，因为他们必然有从根开始的不同的路径从而具有不同的路径名。在 UNIX 文件系统中的目录就是含有它的所有儿子的一个文件。（在 UNIX 文件系统中的每个目录还有一项指向该目录本身以及另一项指向该目录的父目录。因此，严格说来，UNIX 文件系统不是树，而是类树（treelike）。） 假设我们想要列出目录中所文件中所有文件的名字。我们的输出格式将是：深度为 的文件的名字被 次跳格(tab) 锁进后打印出来。 算法的核心为递归程序 ListDir。为了显示根时不进行锁进，该例程需要从目录名和深度 0 开始。这里的深度是一个内部薄记变量，而不是主调例程能够期望知道的那种参数。因此，驱动例程 ListDirectory 用于将递归例程和外界连接起来。 算法的逻辑简单易懂。ListDir 的参数是到树中的某种引用。只要引用合理，则引用涉及的名字在进行适当次数的跳格锁进后被打印出来。如果是一个目录，那么我们递归地一个一个地处理它所有的儿子。这些儿子出在一个深度上，因此需要锁进一段附加的空格。 这种遍历的策略叫做先序遍历（preorder traversal）。在先序遍历中，对节点的处理工作是在它的诸儿子节点被处理之前进行的。当程序运行时，每个父节点恰好最多只执行一次，因为每个名字只输出一次。不仅如此，对于每个节点的每一个儿子节点最多只能执行一次。在遍历过程中，每个 for 循环终止在 NULL 指针上，但每个节点最多有一个这样的指针。因此，每个节点总的工作量是常数。如果有 N 个文件名需要输出，则运行时间就是 O(N)。 另一种遍历树的方法是后序遍历（postorder traversal）。在后序遍历中，在一个节点处的工作是在它的诸儿子节点被计算后进行的。 由于目录本身也是文件，因此它们也有大小。设我们想要计算被该树所有文件占用的磁盘区块的总数。最自然的做法是找出含有子目录中的块的个数。于是，磁盘块的总数就是子目录中的块的总数加上该目录使用的一个块。 如果不是一个目录，那么 SizeDirectory 只返回所占用的块数。否则，将被占用的块数与其所有子节点（递归地）发现的块数相加。