英文翻译0615.docx

英文翻译0615.docx

《英文翻译0615.docx》由会员分享，可在线阅读，更多相关《英文翻译0615.docx（8页珍藏版）》请在冰点文库上搜索。

英文翻译0615

毕业设计（论文）

外文翻译

题目数据结构中图的算法的实现

专业信息管理与信息系统

班级08信管

学生洪斐斐

学号20806019

指导教师胡元义

西安理工大学高科学院

2012年

英文原文

Diagram

Thediagramisthedatastructurethatismanyrightnessestorelatetomoreofakindofdatachemicalelement,plustheabstractdatatypethatasetofbasicoperationconstitutes.

Thedefinitionofdiagram

Thediagram（Graph）topgotemptybynotgathersVandofthedescriptiontoprelation-gatheringofside（orHu）theEconstitute,itformaldefinitionBE:

G=（V,E）

IfeachsideinthediagramGistohavenodirection,thencallGashavenotothediagram.Havenoisahavingnooftopindiagramtowardthesideindiagramprefaceisaccidentallyright.Havenoprefacetoaccidentallymeantowardsusuallyusingaparenthesis"（）".Forexample,topaccidentallyto（vi,vj）thesidethatmeansthattopviandtopvjconnectwitheachother,and（vi,vj）with（vj,vi）meanthesameside.

IfeachsideinthediagramGhasdirectionalof,thencallGforhastowardthediagram.Isahavingoftopindiagramtowardthesideinthediagramprefaceaccidentallyto,thereisprefaceaccidentallytousuallymeanwiththepointbrackets"<>".Forexample,topaccidentallytomeanfromoneofthetopvidirectiontopvjandhavetowardtheside;Amongthem,thetopviiscalledtowardthesideofpointofdeparture,thetopvjiscalledtowardthesideofterminalpoint.AlsobecalledHutotheside;TotheHusay,theviisthepointofdepartureofHu,becalledHutail;ThevjistheterminalpointofHu,becalledaHuhead.

Thediagramiscomplicateddatastructure,expressatnotonlythedegreeofeachtopcanbedifferent,andthelogicofoftoprelatestoalsocomplex.Canknowfromthedefinitionofdiagram:

Theinformationofadiagramincludestwoparts:

Therelation-sideofortheinformationoftheHuoftheinformationandthedescriptiontopoftopindiagram.Consequentlynomatteradoptwhatmethodtobuildupthesavingstructureofdiagram,allhavetobecompleteandaccuratelyreflectthesetwopartsoftheinformations.InordertobesuitablefortodescribewiththeClanguage,riseatopordinalnumberfromthisstanzafrom0beginning,namelythetopofdiagramgatherofgeneralformBE:

V

ThetimeofthediagramLi

ThetimeLiofdiagramisakindofbasicoperationofdiagram,itistosolveconnectingofdiagramsexproblemandTuotorushtowardtolineupaprefaceandbegthefoundationofcalculatewayslikekeypath,etc.ThetimeofthediagramLiusuallyadoptsdepthtohavetheinitiativetosearch（DepthFirstSearch,DFS）andthewidedegreehavetheinitiativetosearch（BreadthFirstSearch,BFS）twokindsofmethods,thesetwokindsofmethodstothetimethathasnotowardthediagramandhastowardthediagramtheLiallapply.

ThewidedegreeofthediagramtimeLi

WidedegreehavetheinitiativetosearchLidiagramismoresimilarthanatreeofbythelayertimeLi.Widedegreethebasicthoughtthathastheinitiativetosearchis:

Thesometopvsetoutfromthediagram,aftervisitingtopvonebyoneinordervisitedagainmutuallyandabuttinglyhavenevervisitedwithvofrestabutmentsidecrunodev1,v2,…,vk;Connectdowntovisitaccordingtotheabove-mentionedmethodagainandvonenevervisitingoftheabutmentoverofeachabutmentsidecrunode,andv2nevervisitingoftheabutmentsesoverofeachabutmentsidecrunode,…,andvkabutmentofhavenevervisitedofeachabutmentsidecrunode;…Keeponpursuingalayerlikethisuntilalltopsinthediagrambevisited.WidedegreethecharacteristicsthathastheinitiativeandsearchesLidiagramisaforerunnerandgoespossiblyhorizontalsearch,namelyandfirstvisitoftopitabutmentsidethecrunodealsovisitfirst,behindvisitoftopitabutmentsidecrunodealsobehindvisit.

ThedepthtimeofthediagramLi

Depth'shasingtheinitiativetosearchisfirstmoresimilarthanatreetothetimeofthediagramLirootthetimeLiisfirstatreerootakindofexpansionoftimeLi;Alsonamely,searchingtheorderofsequenceoftopisalongapathdeeplydeveloptotheZongasfaraspossible.Thebasicthoughtthatthedepthhastheinitiativetosearchis:

Supposebeginning'sstartingstatusisalltopsindiagramhavenevervisited,thedepththenhastheinitiativetosearchcanacertaintopvsetouttonamelyandfirstvisitvfromthediagram,thenonebyoneinorderfromthenevervisitingofthevoveroftheabutmentpointsetoutandcontinuethedepthhavetheinitiativetosearchdiagram,untildiagraminallhavepathwithvthetopsofmutuallybeallvisited;Iftherewasstillatopbeingnotvisitedinginthediagramatthistime,thenchooseanotheratopthathasnevervisitedasthestartorders,processrepeattheabove-mentioneddepthtohavetheinitiativetosearch,untilalltopsinthediagrambevisited.

Connectingofdiagramuniversality

BEcarryingonlastingtowardshavingnotowardthediagram,toconnectdiagramtoonlyneedtheanytopsetouttocarryondepthtohavetheinitiativetosearchfromthediagramorthewidedegreehavetheinitiativetosearch,canvisittoalltopsinthediagram;Fordon'tconnectdiagram,thenneedseveraltopsconnectedbynottostartcarryingontosearch,andeverysetouttocarryonthetopinterviewsearchedtogetintheprocesssequencefromanewtop,bethecontainmentshouldsetouttopoftheconnectweightinofthetopgather.

Therefore,wanttojudgeonetohavenotowardthediagramwhetherinordertoconnectdiagram,orhaveseveralsconnectweight,thencanincrease1tocounttochangetomeasurecountandestablishitthebeginningbeworthto0andhavetheinitiativetosearchthesecondforcirculationinthecalculatewayDFSTraversefunctioninthedepthin,adjusttouseaDFStoincreaseforcounteachtime1;Thecountvaluethatiscalculatewayperformancetoendlikethisforedsthepiecethatconnectsweight.

Arriveotheratallpointlytheshortestpathfromasource

GivetosettleonetotakepowertohavetowardthediagramG=（V,E）,specifythevofacertaintopwithindiagramGtoorderforsourceandbegfromvtothemostshort-circuitpathofofothereachtops;Thisproblemiscalledalistsourcetoorderthemostshort-circuitpathproblem.

DiheroSipulls（Dijkstra）especiallyaccordingtoifpressthelengthincreasedorderofsequencebornordervfromthesource0arrivethemostshort-circuitpathofothertops,thenatpresentjustonthebornlythemostshort-circuitpathinadditiontoterminalpointoutside,themostshort-circuitpathofresttopallalreadybornthisthoughtsandputsforwardtopressthepathlengthincreasedorderofsequencetoproducethecalculatewayofthemostshort-circuitpath.（here,pathlengthforpathlastsideorthepowerofHubeworthitand）ThethoughtofDijkstracalculatewayis:

EstablishtwotopstogatherSandTtowardstakingpowerandhavingtowardthediagramG=（V,E）,=V-S;Anywithv0issource'sorderingtocombineterminalpoints（top）ofmakingsurethemostshort-circuitpathshasalreadyallmergedintotogatherSandgatherSearlyTaiimpliesasourcetoorderv0;Butthetopthathasn'tmadesureitsthemostshort-circuitpathallbelongtogatherT,beginningTaigatherTcontainmentinadditiontothesourceordersv0resttops.Accordingtoeachtopandv0mostshort-circuitpathlengthincreasedorderofsequence,graduallyoneortwogatherthetopintheTtojointogathertogointheS,makethepathlengthofeachtopalwaysbenobiggerthanvfromthesourceorderv0togatherS0togatherthepathlengthofeachtopinT.And,gathertojoinanewtopueachtimeintheS,allwanttomodifyasourcetoorderv0togatherthemostshort-circuitpathlengthofsurplustopinT;Alsonamely,gatheringthelatelythemostshort-circuitpathlengthvalueofeachtopvinTisanoriginallythemostshort-circuitpathlengthvalueoristhemostshort-circuitpathlengthoftoputobeworthagainplusthetopuisworththesetothepathlengthoftopvtwomediumofsmallervalue.ThiskindofgatherthetopintheTtojointogathertheprocessintheScontinuouslyrepeateduntilallofthetopthatgathersTjointogatherSin.

Notice,attogathertoaddtopintheS,alwayskeepthemostshort-circuitpathlengthofeachtoptobenobiggerthanthemostshort-circuitpathlengthofanytopfromthesourceorderv0togatherTfromthesourceorderv0togatherS.Forexample,ifjusttogatheredtoaddintheSofisatopvk,forgathereachtopvuintheT,ifthetopvkarrivedvutohaveaside（establishedthepowervalueasw2）,andoriginallyfromthetopv0arrivethepathlength（establishedthepowervalueasw3）oftopvuwasbiggerthanfromthetopv0arrivethepathlength（establishedthepowervalueasw1）ofthetopvkandthepoweroftheside（vk,vu）wereworthw2itand,namelyw3>ws1+ws2.Thenis0→vksthev→vuthisallthewaythepathisalatelythemostshort-circuitvupath.

译文

图

图是一种数据元素间为多对多关系的数据结构，加上一组基本操作构成的抽象数据类型。

图的定义

图（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}。

图的遍历

图的遍历是图的一种基本操作，它是求解图的连通性问题、拓扑排序以及求关键路径等算法的基础。

图的遍历通常采用深度优先搜索（DepthFirstSearch,DFS）和广度优先搜索（BreadthFirst