如果您无法下载资料,请参考说明:
1、部分资料下载需要金币,请确保您的账户上有足够的金币
2、已购买过的文档,再次下载不重复扣费
3、资料包下载后请先用软件解压,在使用对应软件打开
GRAPHALGORITHMSDefinitions(background):Graph:nodes/vertices,andedges/arcsaspairsofnodes.{V,E}e12=(v1,v2,l12)Thethirdterml12,ifpresent,couldbealabelortheweightofanedge.Directedgraph:edgesareorderedpairsofnodes.Weightedgraph:eachedge(directed/undirected)hasaweight.Pathbetweenapairofnodesvi,vk:sequenceofedgeswithvi,vkatthetwoends.Simplepath:coversnonodeinittwice.Loop:apathwiththesamestartandendnode.Pathlength:numberofedgesinit.Pathweight:totalwtofalledgesinit.Connectedgraph:thereexistsapathbetweeneverynode,nonodeisdisconnected.Completegraph:edgebetweeneverypairofnodes[NUMBEROFEDGES?].Acyclicgraph:agraphwithnocycles.Etc.Graphsareoneofthemostusedmodelsofreal-lifeproblemsforcomputer-solutions.Representations:Adjacencylist(alinklistoranarrayofdirectlyconnectednodesforeachnode),andmatrixaretworepresentations.MatrixisO(N^2)forNnodesbuteasytoaccess,whileadjacencylistisgoodforsparsegraph(sparselydistributededges,lessconnected).Problemsizeincludesboth|V|(numberofnodesN),and|E|(numberofedges,intheworstcaseO(N2)forcompletegraph,butnot“fair”forasparsegraph).Also,withmatrixrepresentation|E|isalwaysN2,becauseonehastogooverallthepairsofnodestocheckwhichonesareinE.Algorithm1:ForeachnodevinVdo-Steps-//(|V|)Algorithm2:ForeachnodevinVdoForeachedgeinEdo-Steps-//(|V|*|E|)Algorithm3:ForeachnodevinVdoForeachedgeeofvdo-Steps-//(|E|)withadjacencylist,but(|V|*|V|)formatrixrepres.Algorithm4:ForeachnodevinVdoForeachnodewadjacenttovdo-Steps-//again,(|E|)withadjacencylistAlgorithm5:ForeachnodevinVdo-steps-Foreachedgeeofvdo-Steps-//(|V|+|E|)or(max{|V|,|E|})TOPOLOGICALSORTInput:directedacyclicgraphOutput:sequentiallyorderthenodeswithoutviolatinganyarcordering.Note:youmayhavetocheckforcycles-dependingontheproblemdefinition(input:directedgraph).Example:coursepre-requisitegraph,findalinearorderingofcourses.Animportantdata:indegreeofeachnode-numberofarcscomingin(#coursespre-requisiteto"this"course).Afirst-passstra