英文翻译0615.docVIP

2012届信息管理与信息系统专业毕业设计（论文）毕业设计（论文）外 文 翻 译 题 目 数据结构中图的算法的实现专 业 信息管理与信息系统 班 级 08信管 学 生 洪斐斐 学 号 20806019 指导教师 胡元义 西安理工大学高科学院 2012 年英文原文Diagram The diagram is the data structure that is many rightnesses to relate to more of a kind of data chemical element, plus the abstract data type that a set of basic operation constitutes.The definition of diagram The diagram(Graph) top got empty by not gathers V and of the description top relation-gathering of side(or Hu) the E constitute, it formal definition BE:G=(V, E)If each side in the diagram G is to have no direction, then call G as have no to the diagram.Have no is a having no of top in diagram toward the side in diagram preface is accidentally right.Have no preface to accidentally mean towards usually using a parenthesis().For example, top accidentally to(vi, vj) the side that means that top vi and top vj connect with each other, and(vi, vj) with(vj, vi) mean the same side.If each side in the diagram G has directional of, then call G for has toward the diagram.Is a having of top in diagram toward the side in the diagram preface accidentally to, there is preface accidentally to usually mean with the point brackets.For example, top accidentally tomean from one of the top vi direction top vj and have toward the side;Among them, the top vi is called toward the sideof point of departure, the top vj is called toward the sideof terminal point.Also be called Hu to the side;To the Hu say, the vi is the point of departure of Hu, be called Hu tail;The vj is the terminal point of Hu, be called a Hu head.The diagram is complicated data structure, express at not only the degree of each top can be different, and the logic of of top relates to also complex.Can know from the definition of diagram:The information of a diagram includes two parts:The relation-side of or the information of the Hu of the information and the description top of top in diagram.Consequently no matter adopt what method to build up the saving structure of diagram, all have to be complete and accurately reflect these two parts of the informations.In order to be suitable for to describe with the C language, rise a top ordinal number from this stanza from 0 beginning, namely the top of diagram gather of general form BE:VThe time of the diagram Li The time Li of diagram is a kind of basic operation of diagram, it is to solve connecting of diagram sex problem and Tuo to rush toward to line up a preface and beg the foundation of calculate ways like key path,etc.The time of the diagram Li usually adopts depth to have the initiative to search(Depth First Search, DFS) and the wide degree have the initiative to search(Breadth First Search, BFS) two kinds of methods, these two kinds of methods to the time that has no toward the diagram and has toward the diagram the Li all apply.The wide degree of the diagram time Li Wide degree have the initiative to search Li diagram is more similar than a tree of by the layer time Li.Wide degree the basic thought that has the initiative to search is:The some top v set out from the diagram, after visiting top v one by one in order visited again mutually and abuttingly have never visited with v of rest abutment side crunode v 1, v 2, , vk;Connect down to visit according to the above-mentioned method again and v one never visiting of the abutment over of each abutment side crunode, and v 2 never visiting of the abutmentses over of each abutment side crunode, , and vk abutment of have never visited of each abutment side crunode;Keep on pursuing a layer like this until all tops in the diagram be visited.Wide degree the characteristics that has the initiative and searches Li diagram is a forerunner and goes possibly horizontal search, namely and first visit of top it abutment side the crunode also visit first, behind visit of top it abutment side crunode also behind visit.The depth time of the diagram Li Depths hasing the initiative to search is first more similar than a tree to the time of the diagram Li root the time Li is first a tree root a kind of expansion of time Li;Also namely, searching the order of sequence of top is along a path deeply develop to the Zong as far as possible.The basic thought that the depth has the initiative to search is:Suppose beginnings starting status is all tops in diagram have never visited, the depth then has the initiative to search can a certain top v set out to namely and first visit v from the diagram, then one by one in order from the never visiting of the v over of the abutment point set out and continue the depth have the initiative to search diagram, until diagram in all have path with v the tops of mutually be all visited;If there was still a top being not visiteding in the diagram at this time, then choose another a top that has never visited as the start orders, process repeat the above-mentioned depth to have the initiative to search, until all tops in the diagram be visited.Connecting of diagram universality BE carrying on lasting towards having no toward the diagram, to connect diagram to only need the any top set out to carry on depth to have the initiative to search from the diagram or the wide degree have the initiative to search, can visit to all tops in the diagram;For dont connect diagram, then need several tops connected by not to start carrying on to search, and every set out to carry on the top interview searched to get in the process sequence from a new top, be the containment should set out top of the connect weight in of the top gather.Therefore, want to judge one to have no toward the diagram whether in order to connect diagram, or have severals connect weight, then can increase 1 to count to change to measure count and establish it the beginning be worth to 0 and have the initiative to search the second for circulation in the calculate way DFSTraverse function in the depth in, adjust to use a DFS to increase for count each time 1;The count value that is calculate way performance to end like this foreds the piece that connects weight.Arrive other at all pointly the shortest path from a source Give to settle one to take power to have toward the diagram G=(V, E), specify the v of a certain top within diagram G to order for source and beg from v to the most short-circuit path of of other each tops;This problem is called a list source to order the most short-circuit path problem.Di hero Si pulls(Dijkstra) especially according to if press the length increased order of sequence born order v from the source 0 arrive the most short-circuit path of other tops, then at present just on the bornly the most short-circuit path in addition to terminal point outside, the most short-circuit path of rest top all already born this thoughts and puts forward to press the path length increased order of sequence to produce the calculate way of the most short-circuit path.(here, path length for path last side or the power of Hu be worth it and)The thought of Dijkstra calculate way is:Establish two tops to gather S and T towards taking power and having toward the diagram G=(V, E), =V-S;Any with v 0 is sources ordering to combine terminal points(top) of making sure the most short-circuit paths has already all merged into to gather S and gather S early Tai implies a source to order v 0;But the top that hasnt made sure its the most short-circuit path all belong to gather T, beginning Tai gather T containment in addition to the source orders v 0 rest tops.According to each top and v 0 most short-circuit path length increased order of sequence, gradually one or two gather the top in the T to join to gather to go in the S, make the path length of each top always be no bigger than v from the source order v 0 to gather S 0 to gather the path length of each top in T.And, gather to join a new top u each time in the S, all want to modify a source to order v 0 to gather the most short-circuit path length of surplus top in T;Also namely, gathering the lately the most short-circuit path length value of each top v in T is an originally the most short-circuit path length value or is the most short-circuit path length of top u to be worth again plus the top u is worth these to the path length of top v two medium of smaller value.This kind of gather the top in the T to join to gather the process in the S continuously repeated until all of the top that gathers T join to gather S in.Notice, at to gather to add top in the S, always keep the most short-circuit path length of each top to be no bigger than the most short-circuit path length of any top from the source order v 0 to gather T from the source order v 0 to gather S.For example, if just to gathered to add in the S of is a top vk, for gather each top vu in the T, if the top vk arrived vu to have a side(established the power value as w 2), and originally from the top v 0 arrive the path length(established the power value as w 3) of top vu was bigger than from the top v 0 arrive the path length(established the power value as w 1) of the top vk and the power of the side(vk, vu) were worth w 2 it and, namely w 3 ws 1+ ws 2.Then is 0 vks the v vu this all the way the path is a lately the most short-circuit vu path.译文图图是一种数据元素间为多对多关系的数据结构，加上一组基本操作构成的抽象数据类型。图的定义图（Graph）是由非空的顶点集合V与描述顶点之间关系边（或者弧）的集合E组成，其形式化定义为：G=(V, E) 如果图G中的每一条边都是没有方向的，则称G为无向图。无向图中边是图中顶点的无序偶对。无序偶对通常用圆括号“( )”表示。例如，顶点偶对(vi,vj)表示顶点vi和顶点vj相连的边，并且(vi,vj)与(vj,vi)表示同一条边。 如果图G中的每一条边都是有方向的，则称G为有向图。有向图中的边是图中顶点的有序偶对，有序偶对通常用尖括号“”表示。例如，顶点偶对表示从顶点vi指向顶点vj的一条有向边；其中，顶点vi称为有向边的起点，顶点vj称为有向边的终点。有向边也称为弧；对弧来说，vi为弧的起点，称为弧尾；vj为弧的终点，称为弧头。图是一种复杂的数据结构，表现在不仅各顶点的度可以不同，而且顶点之间的逻辑关系也错综复杂。从图的定义可知：一个图的信息包括两个部分：图中顶点的信息以及描述顶点之间的关系边或弧的信息。因此无论采取什么方法来建立图的存储结构，都要完整、准确地反映这两部分的信息。为适于用C语言描述，从本节起顶点序号由0开始，即图的顶点集的一般形式为：V=v0,v1,vn-1。 图的遍历图的遍历是图的一种基本操作，它是求解图的连通性问题、拓扑排序以及求关键路径等算法的基础。图的遍历通常采用深度优先搜索（Depth First Search,DFS）和广度优先搜索（Breadth First Search,BFS）两种方式，这两种方式对无向图和有向图的遍历都适用。 图的广度遍历 广度优先搜索遍历图类似于树的按层次遍历。广度优先搜索的基本思想是：从图中某顶点v出发，访问顶点v后再依次访问与v相邻接的未曾访问过的其余邻接边结点v1，v2，vk；接下来再按上述方法访问与v1邻接的未曾访问过的各邻接边结点、与v2邻接的未曾访问过的各邻接边结点、与vk邻接的未曾访问过的各邻接边结点；这样逐层下去直至图中的全部顶点都被访问过。广度优先搜索遍历图的特点是尽可能先进行横向搜索，即先访问的顶点其邻接边结点也先访问，后访问的顶点其邻接边结点也后访问。图的深度遍历深度优先搜索对图的遍历类似于树的先根遍历，是树的先根遍历的一种推广；也即，搜索顶点的次序是沿着一条路径尽量向纵深发展。深度优先搜索的基本思想是：假设初始状态是图中所有顶点都未曾访问过，则深度优先搜索可以从图中某个顶点v出发即先访问v，然后依次从v的未曾访问过的邻接点出发，继续深度优先搜索图，直至图中所有和v有路径相通的顶点都被访问过；若此时图中尚有顶点未被访问过，则另选一个未曾访问过的顶点作为起始点，重复上述深度优先搜索的过程，直到图中的所有顶点都被访问过为止。图的连通性 在对无向图进行遍历时，对连通图仅需从图中任一顶点出发进行深度优先搜索或广度优先搜索，就可访问到图中的所有顶点；对于非连通图，则需要由不连通的多个顶点开始进行搜索，且每一次从一个新的顶点出发进行搜索过程中得到的顶点访问序列，就是包含该出发顶点的这个连通分量中的顶点集。因此，要想判断一个无向图是否为连通图，或者有几个连通分量，则可增加一个计数变量count并设其初值为0，在深度优先搜索算法DFSTraverse函数里的第二个for循环中，每调用一次DFS就给count增1；这样当算法执行结束时的count值即为连