Data Structure(C++) Slides-ENG 数据结构课件Chapter-6-Graph-English

2020DataStructures

Chapter6GraphBasicConceptsofGraphs6.16.1IntroductiontoGraphsDataStructuresChapter6GraphEuler(1707-1783)isregardedbysomehistoriansasoneofthetwogreatestmathematiciansinhistory;hisnameappearsinnearlyeveryfieldofmathematics.Eulerlineinelementarygeometry,Euler'stheoremforpolyhedra,Eulertransformationsinsolidanalyticgeometry,Euler'ssolutionofquarticequations,Euler'sfunctioninnumbertheory,Eulerequationsindifferentialequations,Euler'sconstantinseriestheory,Eulerequationsinvariationalcalculus,Euler'sformulaincomplexfunctions,andmore.Eulercompleted886booksandpapersinhislifetime:analysis,algebra,andnumbertheory40%;geometry18%;physicsandmechanics28%;astronomy11%;ballistics,navigation,architecture,etc.3%.HissolutiontothefamousKonigsbergSevenBridgesproblemopenedthestudyofgraphtheory.Whatcandriveapersontodevotealifetimetoonepursuit?6.1Canonestartfromsomeplace,crosseachbridgeexactlyonce,andreturntothestartingpoint?KonigsbergSevenBridgesDataStructuresChapter6GraphIntroductiontoGraphs6.1Euler'sAnalysis

Exceptforthestartingpoint,wheneveroneentersapointoverabridge,onemustalsoleaveitoveranotherbridge;thustwobridgesarecountedateachpoint.Thebridgeleavingthestartingpointandthebridgefinallyreturningtoitarealsocountedastwobridges.Therefore,thenumberofbridgesconnectingeachlandareatotheothersmustbeeven.ThisleadstothefamousEulercircuit.

Anyconnectedgraphconsistingonlyofeven-degreeverticescanbedrawninonestroke.Startingfromanyevenvertex,thedrawingcanendatthesamevertex.Anyconnectedgraphwithexactlytwoodd-degreeverticescanbedrawninonestroke.Oneoddvertexmustbethestartandtheothertheend.Allothergraphscannotbedrawninonestroke.CADBDataStructuresChapter6GraphIntroductiontoGraphs6.1DefinitionofaGraphAgraphconsistsofafinitenonemptysetofverticesandasetofedgesbetweenvertices,usuallywrittenas:

G=(V，E)whereGdenotesagraph,VisthesetofverticesinG,andEisthesetofedgesbetweenverticesinG.Alinearlistmaybeempty,withzeroelements;Atreemaybeempty,withzeronodes;Butagraphcannothavezerovertices,althoughitmayhavenoedges.DataStructuresChapter6Graph6.1BasicConceptsofGraphsIftheedgesbetweenanytwoverticesofagraphareallundirected,thegraphiscalledanundirectedgraph.Iftheedgebetweenverticesviandvjhasnodirection,itiscalledanundirectededgeandisdenoted(vi,vj).Iftheedgefromvertexvitovjhasadirection,itiscalledadirectededgeandisdenoted<vi,vj>.Iftheedgesbetweenanytwoverticesofagrapharealldirected,thegraphiscalledadirectedgraph.V1V2V3V4V5V1V2V3V4DataStructuresChapter6Graph6.1Simplegraph:agraphwithnoedgefromavertextoitselfandnorepeatededge.BasicConceptsofGraphsIndatastructures,wediscusssimplegraphs.V3V4V5V1V2V3V4V5V1V2V3V4V5V1V2DataStructuresChapter6Graph6.1BasicConceptsofGraphsAdjacencyandIncidence:Inanundirectedgraph,foranytwoverticesviandvj,ifedge(vi，vj)exists,viandviareadjacent,andedge(vi，vj)isincidentonviandvj.ViVjV3V4V5V1V2AdjacentverticesofV1:AdjacentverticesofV2:DataStructuresChapter6Graph6.1BasicConceptsofGraphsAdjacencyandIncidence:Inadirectedgraph,foranytwoverticesviandvj,ifarc<vi，vj>exists,viisadjacenttovj,vjisadjacentfromvi,andarc<vi，vj>isincidentonviandvj.ViVjV1V2V3V4VerticesadjacentfromV1:

VerticesadjacenttoV1:DataStructuresChapter6Graph6.1ComparisonofThreeBasicDataStructuresFECBADLinearListABCDEFTreeInalinearstructure,dataelementshaveonlyalinearrelationship:predecessorandsuccessor.Inatreestructure,nodeshaveahierarchicalrelationship:parentandchild.Inagraphstructure,anytwoverticesmayberelated:adjacency.V3V4V5V1V2GraphDataStructuresChapter6Graph6.1BasicConceptsofGraphsUndirectedcompletegraph:inanundirectedgraph,ifanedgeexistsbetweeneverypairofvertices,thegraphiscalledanundirectedcompletegraph.Directedcompletegraph:inadirectedgraph,iftwooppositelydirectedarcsexistbetweeneverypairofvertices,thegraphiscalledadirectedcompletegraph.V1V2V3V4V1V2V3Anundirectedcompletegraphwithnverticeshasn*(n-1)/2edges.Adirectedcompletegraphwithnverticeshasn*(n-1)edges.DataStructuresChapter6Graph6.1ClassroomExercise1.IfanundirectedgraphGhasnvertices,thenGhasatleast()edgesandatmost()edges;ifGisadirectedgraph,thenGhasatleast()edgesandatmost()edges;2.Gisadisconnectedundirectedgraphwith28edges.Whatistheminimumnumberofvertices?A.6B.7C.8D.9DataStructuresChapter6GraphBasicConceptsofGraphs6.1Sparsegraph:agraphwithfewedges.Densegraph:agraphwithmanyedges.Degreeofavertex:inanundirectedgraph,thedegreeofvertexvisthenumberofedgesincidentonit,denotedTD(v).Indegreeofavertex:inadirectedgraph,theindegreeofvertexvisthenumberofarcswhoseheadisv,denotedID(v).Outdegreeofavertex:inadirectedgraph,theoutdegreeofvertexvisthenumberofarcswhosetailisv,denotedOD(v).DegreeofV1:V3V4V5V1V2V1V2V3V4IndegreeofV1:OutdegreeofV1:DataStructuresChapter6GraphBasicConceptsofGraphs6.1ClassroomExercise:InanundirectedgraphGwithnverticesandeedges,findtherelationshipbetweenthesumofvertexdegreesande.InadirectedgraphGwithnverticesandeedges,whatistherelationshipbetweenthesumofindegreesandthesumofoutdegrees?Howdotheyrelatetoe?AnundirectedgraphGhas16edges;3verticeshavedegree4,4verticeshavedegree3,andallremainingverticeshavedegreelessthan3.ThenGhasatleast()vertices.V3V4V5V1V2V1V2V3V4Solution:32=4*3+3*4+(x-7)*2x=11DataStructuresChapter6GraphBasicConceptsofGraphs6.1Path:InanundirectedgraphG=(V,E),apathfromvertexvptovertexvqisavertexsequence(vp=vi0,vi1,vi2,…,vim=vq),where(vij-1,vij)∈E（1≤j≤m）.IfGisadirectedgraph,thepathalsohasdirection,andthevertexsequencesatisfies<vij-1,vij>∈EV3V4V5V1V2PathfromV1toV4:V1V2V3V4Pathfrom

V1toV4:DataStructuresChapter6GraphBasicConceptsofGraphs6.1Weight:ameaningfulnumericalvalueassignedtoanedge.Network:aweightedgraph,alsocalledanetworkgraph.Pathlength:V3V4V5V1V2Unweightedgraph--numberofedgesonthepathWeightedgraph--sumoftheweightsofalledgesonthepathV1V2V3V4V5256328DataStructuresChapter6GraphBasicConceptsofGraphs6.1Circuit(cycle):apathwhosefirstvertexandlastvertexarethesame.

Simplepath:apathinwhichnovertexappearsmorethanonce.

Simplecircuit(simplecycle):acircuitinwhichnoverticesrepeatexceptthefirstandlastvertices.V1V2V3V4V1V2V3V4V5DataStructuresChapter6GraphBasicConceptsofGraphs6.1Subgraph:IfgraphG=（V，E）andG'=（V'，E'）,andV'

VandE'

E

,thenG'iscalledasubgraphofG.V1V2V3V4V5V1V2V3V4V1V3V4V5DataStructuresChapter6GraphBasicConceptsofGraphs6.1Connectedgraph:verticesviandvj

(i≠j)areconnectedifapathexistsbetweenthem.Ifeverypairofverticesisconnected,thegraphisconnected.Connectedcomponent:amaximalconnectedsubgraphofadisconnectedgraph.V1V2V3V4V51.connectedvertices2.incidentedgesDataStructuresChapter6GraphBasicConceptsofGraphs6.1ConnectedComponent1V1V2V3V4V5V6V7V1V2V4V5V3V6V7ConnectedComponent2Connectedcomponent:1.connectedvertices2.incidentedgesV3V7V3V6V7DataStructuresChapter6GraphBasicConceptsofGraphs6.1Stronglyconnectedgraph:Inadirectedgraph,foranypairofverticesviandvj

(i≠j),iftherearepathsfromvitovjandfromvjtovi,thedirectedgraphiscalledstronglyconnected.

Stronglyconnectedcomponent:amaximalstronglyconnectedsubgraphofanon-stronglyconnectedgraph.V2V1V3V4V1V3V4V2StronglyConnectedComponent1StronglyConnectedComponent2DataStructuresChapter6GraphBasicConceptsofGraphs6.1Spanningtree:AspanningtreeofaconnectedgraphGwithnverticesisaminimalconnectedsubgraphthatcontainsallverticesofG.Containsn-1edgesMoreLessV1V2V3V4V5V1V2V3V4V5Connectedandacyclic--formsacircuit

--disconnectedDataStructuresChapter6GraphBasicConceptsofGraphs6.1Spanningforest:Inadisconnectedgraph,eachconnectedcomponentcanproduceaspanningtree;together,thesespanningtreesformaspanningforestofthedisconnectedgraph.V1V2V3V4V5V6V7V1V2V4V5V3V6V7DataStructuresChapter6GraphBasicConceptsofGraphs6.1AbstractDataTypeofGraphADTGraph{Dataobject:D={ai|ai∈ElemSet,i=1,2,...,n,n>=0};aimaybeanydata.Datarelation:R={<ai-1,ai>|ai-1,ai∈D,i=2,...,n};ai-1andaihaveamany-to-manyrelationship.Basicoperations:initGraph:initializeagraph.destroyGraph:destroythegraphandreleaseitsstorage.dfTraverse:depth-firsttraversal,outputtingthetraversalsequence.bfTraverse:breadth-firsttraversal,outputtingthetraversalsequence.}DataStructuresChapter6Graph6.1GraphTraversalDepth-firsttraversal-similartopreordertraversalofatree1.Visitvertexv;2.Selectanunvisitedadjacentvertexwofv,andperformdepth-firsttraversalfromw;3.Repeatthetwostepsaboveuntilallverticesconnectedtovbypathshavebeenvisited.？Usewhichstructureforrecursion?StackDataStructuresChapter6Graph6.1Depth-FirstTraversalofaGraphV1V3V2V4V5V6V7V8

V1V1V2

V2V4

V4V5

V5Traversalsequence:DataStructuresChapter6Graph6.1V1V3V2V4V5V6V7V8

V1V1V2

V2V4

V4V5V8

V8DataStructuresChapter6GraphDepth-FirstTraversalofaGraphTraversalsequence:6.1V1V3V2V4V5V6V7V8

V1V1V2

V2V4

V4V5V8DataStructuresChapter6GraphDepth-FirstTraversalofaGraphTraversalsequence:6.1V1V3V2V4V5V6V7V8

V1V1

V7V2V4V5V8V3

V3V6

V6V7DataStructuresChapter6GraphDepth-FirstTraversalofaGraphTraversalsequence:6.1GraphTraversalBreadth-firsttraversal-similartolevel-ordertraversalofatree

1.Visitvertexv0;2.Visiteachunvisitedadjacentvertexv1,v2,…,vkofv0inorder;3.Startingfromv1,v2,…,vk,visittheirunvisitedadjacentverticesinorder.4.Continuevisitingadjacentverticeslevelbyleveluntilallverticesconnectedtov0bypathshavebeenvisited.DataStructuresChapter6Graph6.1Breadth-FirstTraversalofaGraphV1V3V2V4V5V6V7V8V1V1DataStructuresChapter6GraphTraversalsequence:6.1V1V3V2V4V5V6V7V8V1V2V2V3V3DataStructuresChapter6GraphBreadth-FirstTraversalofaGraphTraversalsequence:6.1V1V3V2V4V5V6V7V8Traversalsequence:V1V2V3V3V4V4V5V5DataStructuresChapter6GraphBreadth-FirstTraversalofaGraph6.1V1V3V2V4V5V6V7V8Traversalsequence:V1V2V3V4V4V5V5V6V6V7V7DataStructuresChapter6GraphBreadth-FirstTraversalofaGraph6.1V1V3V2V4V5V6V7V8Traversalsequence:V1V2V3V4V5V5V6V6V7V7V8V8DataStructuresChapter6GraphBreadth-FirstTraversalofaGraphAdjacencyMatrix6.26.2GraphStorageLogicalFeaturesofGraphsAgraphconsistsofverticesandedges.Edgesmayexistbetweenanytwovertices.Therelationshipbetweenverticesism:n,amany-to-manyrelationship.GraphStorageGraphstorageisusuallyconsideredintwoparts:VerticesEdgesGraphStorageMethodsTwocommonmethods

AdjacencymatrixAdjacencylistDataStructuresChapter6Graph6.2AdjacencyMatrixDefinitionofadjacencymatrix:AssumegraphG=(V,E)hasnvertices.Itsadjacencymatrixisann*nsquarematrix,definedas:

？Storesverticesoredges?？Howshouldverticesbestored?EdgesOne-dimensionalarrayDataStructuresChapter6Graphor6.2AdjacencyMatrixofanUndirectedGraphV1V3V4V2Itisasymmetricmatrix.Themaindiagonalis0.Whatarethecharacteristicsofanundirectedgraph'sadjacencymatrix?？edge[][]=DataStructuresChapter6Graph6.2V1V3V4V2Howtodeterminewhetheranedgeexistsbetweenverticesiandj?？Howtofindtheadjacentverticesofvertexi?？edge[][]=DataStructuresChapter6GraphAdjacencyMatrixofanUndirectedGraph6.2Howdoyoufindoutdegreeofvertexi?？Howdoyoufindindegreeofvertexi?？V1V2V3V4Howtodeterminewhetheranedgeexistsfromvertexitovertexj?？edge[][]=DataStructuresChapter6GraphAdjacencyMatrixofanUndirectedGraph6.2AdjacencyMatrixofaNetworkGraph

V1V2V3V4MathematicaldefinitionHowtorepresentinfinity?？edge[][]=DataStructuresChapter6Graph6.2ClassDefinitionofAdjacencyMatrixClassdefinitionforstoringanundirected

graphwithanadjacencymatrixtemplate<typenameElement>classAMGraph{public:AMGraph();~AMGraph(){};voidbfTraverse(intv);voiddfTraverse(intv);private:Elementvertex[MaxSize];intedge[MaxSize][MaxSize];intvertexNum,edgeNum;};//constructor//destructorisempty//breadth-firsttraversal//depth-firsttraversal//vertexarray//two-dimensionaladjacency-matrixarrayDataStructuresChapter6Graph6.2ConstructionofAdjacencyMatrixCoreconstructorcode(undirectedgraph):for(i=0;i<vertexNum;i++)cin>>vertex[i];//inputvertexdatafor(i=0;i<vertexNum;i++)//initializeadjacencymatrixfor(j=0;j<vertexNum;j++)edge[i][j]=0;for(k=0;k<edgeNum;k++){//inputeachedgeinordercin>>i>>j;//indicesofthetwoverticesincidentontheedgeedge[i][j]=;edge[j][i]=;};11DataStructuresChapter6Graph6.2AdjacencyMatrixDepth-firsttraversalcorecode:voidAMGraph::dfTraverse(intv){visited[v]=true;cout<<vertex[v];for(intw=0;w<vertexNum;w++){if(edge[v][w]==&&!visited[w])dfTraverse(w);}}Depth-firsttraversalVisitvertexv;Selectanunvisitedadjacentvertexwofv,andperformdepth-firsttraversalfromw;Repeatthetwostepsaboveuntilallverticesconnectedtovbypathshavebeenvisited.1DataStructuresChapter6Graph6.2Breadth-firsttraversalVisitvertexv;Visiteachunvisitedadjacentvertexv1,v2,…,vkofvinorder;Startingrespectivelyfromv1,v2,…,vk,visittheirunvisitedadjacentverticesinorder,andmaketheadjacentverticesofearliervisitedverticesbevisitedbeforethoseoflatervisitedvertices.Continueuntilallverticesconnectedtovbypathshavebeenvisited.DataStructuresChapter6GraphAdjacencyMatrix6.2Breadth-FirstTraversalBreadth-firsttraversalcorecode:front=rear=-1;//useaqueueasauxiliarystorage;assumenooverflowcout<<vertex[v];visited[v]=1;Q[++rear]=v;//enqueueaftervisitingwhile(front!=rear){v=Q[++front];for(j=0;j<vertexNum;j++)if(edge[][]==1&&visited[j]==0){cout<<vertex[j];visited[j]=1;Q[++rear]=j;}}vjDataStructuresChapter6Graph6.2ProsandConsofAdjacencyMatrixSimple,intuitive,andeasytounderstandStores0evenwhennoedgeexists,wastingspaceDisadvantagesAdvantagesO(n2)SpacecomplexityDataStructuresChapter6GraphAdjacencylist6.36.3AdjacencylistSimilartothechildlinked-listrepresentationofatreeACBHFEDGIDataStructuresChapter6Graph6.3Definitionofadjacencylist:Foreachvertexviofagraph,linkallverticesadjacenttoviintoasinglylinkedlist,calledtheedgelistofvertex

vi(ortheoutgoing-edgelistforadirectedgraph).Theheadpointersofalledgelistsandtheone-dimensionalarraystoringvertexinformationformthevertexlist.vertex:datafield,storesvertexinformation.firstedge:pointerfield,pointstothefirstnodeintheedgelist.adjvex:adjacent-vertexfield,storesthesubscriptoftheendpointinthevertexlist.next:pointerfield,pointstothenextnodeintheedgelist.vertexfirstedgeVertexlistadjvexnextEdgelistDataStructuresChapter6GraphAdjacencylist6.3AdjacencyListofanUndirectedGraphV1V3V4V2Spacecomplexity?？AnadjacentedgeEdge-listnode?？O(n+2e)=O(n+e)Howtofindthedegreeofvertexi?？Edge-listnodecountDataStructuresChapter6Graph6.3AdjacencyListofaDirectedGraphIndegreeofvertexi?？Nodesini'soutgoinglistOutdegreeofvertexi?？V1V2V3V4Nodesendingatiinallout-listsDirectedgraphsuseoutgoing-edgelistsDataStructuresChapter6Graph6.3AdjacencyListofaNetworkGraphV1V2V3V4DataStructuresChapter6Graph6.3ClassroomExercise1.Drawthegraphfromtheadjacencylist.2.Drawthegraphfromtheadjacencymatrix.DataStructuresChapter6Graph6.3NodeDefinitionofAdjacencyListvertexfirstedgeVertexlistadjvexnextEdgeliststructEdgeNode{intadjvex;*next;};template<classE>structVertexNode{Evertex;*firstedge;};EdgeNodeEdgeNodeDataStructuresChapter6Graph6.3ConstructionofAdjacencyListClassdefinitionforstoringadirected

graphwithanadjacencylistconstintMaxSize=10;//maximumnumberofverticesinthegraphtemplate<classT>classALGraph{public:ALGraph(Ta[],intn,inte);~ALGraph;voidbfTraverse(intv);voiddfTraverse(intv);private:VertexadjList[MaxSize];intvertexNum,edgeNum;};DataStructuresChapter6Graph6.3Coreconstructorcode(directedgraph):for(i=0;i<vertexNum;i++){//inputvertexinformationandinitializeedgelistcin>>adjList[i].vertex;adjList[i].firstedge=nullptr;}for(k=0;k<edgeNum;k++){//inputedgeinformationandstoreitintheedgelistcin>>v1>>v2;s=newedgeNode;s->adjvex=v2s->next=adjList[v1].firstedge;adjList[v1].firstedge=s;}//insertbyheadinsertionDataStructuresChapter6GraphConstructionofAdjacencyList6.3Depth-firsttraversalcorecode:voidMGraph::DFSTraverse(intv){cout<<adjList[v].vertex;//visitcurrentnodevisited[v]=1;//visitedflagp=adjList[v].firstedge;//getthefirstnodeintheedgelistwhile(p!=nullptr){j=p->adjvex;if(visited[j]==0)dfTraverse(j);//recursionp=p->next;}}DataStructuresChapter6GraphAdjacencylist6.3Breadth-firsttraversalcorecode:front=rear=-1;//useaqueueasauxiliarystorage;assumenooverflowcout<<adjList[v].vertex;visited[v]=1;Q[++rear]=v;//enqueueaftervisitingwhile(front!=rear){v=Q[++front];p=adjList[v].firstedge;while(p!=nullptr){j=p->adjvex;if(visited[j]==0){cout<<adjList[j].vertex;visited[j]=1;Q[++rear]=j;}p=p->next;}}DataStructuresChapter6GraphAdjacencylist6.3OtherGraphStorageMethodsAdjacencyListandInverseAdjacencyListV1V2V3V4Adj.ListInverseadjacencylistDataStructuresChapter6Graph6.3OrthogonalListDescribesdirectedgraphsCombinationofadjacencylistandinverseadjacencylistNodestructure:vertexfirstinfirstoutVertex-listnodetailvexheadvexheadlinktaillinkEdge-listnodevertex:datafield,storesvertexinformation;firstin:headpointeroftheincoming-edgelist;firstout:headpointeroftheoutgoing-edgelist;tailvex:subscriptofthearctailinthevertexlist;headvex:subscriptofthearcheadinthevertexlist;headlink:pointerfieldfortheincoming-edgelist;taillink:pointerfieldfortheoutgoing-edgelist.DataStructuresChapter6GraphOtherGraphStorageMethods6.3StoragePrincipleofOrthogonalListV1V2V3V4DataStructuresChapter6GraphOtherGraphStorageMethods6.3AdjacencyMultilist

Anundirectedgraph'sadjacencyliststoreseachedgetwice;theadjacencymultilistimprovesthis.V1V2V3V4Inanadjacencymultilist,eachedgecorrespondstoonlyonenode,improvingefficiencyforsomeoperations.Itsstructureresemblestheorthogonallistfordirectedgraphs,butitsapplicationscenarioislessclear,constructionislessintuitiveandconvenient,andedgeoperationsmayneedadditionalchecks.Overall,itisusedlessfrequently.DataStructuresChapter6GraphOtherGraphStorageMethods6.3StorageStructureComparisonO(n2)O(n+e)O(n2)O(n+e)SpaceperformanceTimeperformanceSuitablerangeUniquenessAdjacencyMatrixAdjacencyListDensegraphSparsegraphUniqueNotuniqueComparisonofGraphStorageStructures-AdjacencyMatrixandAdjacencyListDataStructuresChapter6Graph6.3ChapterAssignmentandLab

Chapterlab:implementtwotraversaloperationsforanundirectednetworkgraph.Chapterassignment:thefollowingtablegivesthetraveldistancesamongsixworldcities:Beijing(Pe),NewYork(N),Paris(Pa),London(L),Tokyo(T),andMexicoCity(M).

PeNPaLTMPe

109828121124N109

585510832Pa8258

39792L81553

9589T211089795

113M124329289113

1.Drawthetransportationnetworkgraph.2.Drawtheadjacency-listrepresentationofthegraph.3.(Optionallab)ConstructtheminimumspanningtreeusingPrimandKruskalalgorithms.4.(Optionallab)FindshortestpathsfromBeijingasthesourceusingDijkstra'salgorithm.DataStructuresChapter6GraphMinimumSpanningTree6.46.4MinimumSpanningTreeSpanningtree:AspanningtreeofconnectedgraphGwithnnodesisaminimalconnectedsubgraphcontainingallnconnectedverticesandn-1edges.Aspanningtreeofaconnectedgraphcanbeobtainedbytraversal,e.g.,adepth-firstspanningtreeorbreadth-firstspanningtree.Foradisconnectedgraph,traversalproducesaspanningforest.(a)Depth-firstspanningtree(b)Breadth-firstspanningtreeV1V3V2V4V5V6V7V1V3V2V4V5V6V7DataStructuresChapter6Graph6.4Thespanningtreeofthesameconnectedgraphmaynotbeunique;differenttraversalorderscanproducedifferentspanningtrees.Costofaspanningtree:thesumoftheweightsofalledgesinaspanningtreeofgraphG.Minimumspanningtree:IfG=(V,E)isanundirectedconnectednetwork,thespanningtreeofGwiththeminimumcostiscalledaminimumspanningtree(MST).Theconceptofaminimumspanningtreeappliestomanypracticalproblems.Networkandlinedeploymentproblems:minimizetotalcost.Example:TobuildanInternetnetworkamongncities,atleastn-1linesareneeded,andthecostofequipmentbetweeneachpairofcitiesdiffers.Howshouldthenetworkbedesignedtominimizetotalcost?Transportationnetworkplanning,communicationnetworkplanning,circuit-boarddesign.Mapcoloring.Clusteringanalysis,networktaskassignment,etc.DataStructuresChapter6GraphMinimumSpanningTree6.4Keyproperty:LetG=(V,E)beanundirectedconnectednetwork,andletUbeanonemptysubsetofvertexsetV.If(u,v)isanedgewithminimumweightwhereu∈Uandv∈V－U,thenthereexistsaminimumspanningtreecontainingedge(u,v).TheMSTpropertycanbeusedtoconstructaminimumspanningtree.Prim'salgorithmKruskal'salgorithmVertexsetUV－UVertexsetu'vv'uDataStructuresChapter6GraphMinimumSpanningTree6.4Prim'sAlgorithmAlgorithmorigin:DiscoveredbyCzechmathematicianVojtechJarnikin1930.ProposedbyAmericancomputerscientistRobertPrimin1957.AlsostudiedbyDijkstrain1959.

Algorithmidea:

LetG=(V,E)beaconnectednetworkwithnvertices,andletT=T=(U,TE)betheminimumspanningtreeofG.

InitialstateofT:U={u0}(u0inV),TE={}.Repeatthefollowingoperation:Amongalledgeswithu∈Uandv∈V-U,findtheedge(u,v)withminimumcostandaddittoTE.Atthesametime,addvtoU,untilU=V.DataStructuresChapter6Graph6.4Prim'sAlgorithmU=V-U=cost={(A,B)(A,C)(A,D)(A,E)(A,F)}TE={(A,F,19)}251234192646381725ABEDCFDataStructuresChapter6Graph6.4Prim'sAlgorithmU=V-U=cost={(A,B)(F,C)(F,D)(F,E)}TE={(A,F,19),(F,C,25)}251234192646381725ABEDCFDataStructuresChapter6Graph6.4Prim'sAlgorithmU=V-U=cost={(A,B)(C,D)(F,E)}TE={(A,F,19),(F,C,25),(C,D,17)}251234192646381725ABEDCFDataStructuresChapter6Graph6.4Prim'sAlgorithmU=V-U=cost={(A,B)(F,E)}TE={(A,F,19),(F,C,25),(C,D,17),(F,E,26)}251234192646381725ABEDCFDataStructuresChapter6Graph6.4Prim'sAlgorithmU=V-U=cost={(E,B)}TE={(A,F,19),(F,C,25),(C,D,17),(F,E,26),(E,B,12)}

251234192646381725ABEDCFDataStructuresChapter6