资源描述：
《Data Structures with C++ using STL Chapter 161》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1MainIndexContentsGraphCategoriesExampleofDigraphConnectednessofDigraphAdjacencyMatrixAdjacencySetvertexInfoObjectVertexMapandVectorvInfoVtxMapandVinfoExampleBreadth-FirstSearchAlgorithm(2slides)Dfs()Chapter16–GraphsStrongComponentsGraphGandItsTransposeGT
2、Shortest-PathExample(2slides)DijkstraMinimum-PathAlgorithm(2slides)MinimumSpanningTreeExampleMinimumSpanningTree:verticesAandBCompletingtheMinimumSpanning-TreewithVerticesCandDSummarySlides(4slides)12MainIndexContentsGraphCategoriesAgraphisconnectedifeach
3、pairofverticeshaveapathbetweenthemAcompletegraphisaconnectedgraphinwhicheachpairofverticesarelinkedbyanedge23MainIndexContentsExampleofDigraphGraphwithorderededgesarecalleddirectedgraphsordigraphs34MainIndexContentsConnectednessofDigraphStronglyconnectedi
4、fthereisapathfromanyvertextoanyothervertex.Weaklyconnectedif,foreachpairofverticesviandvj,thereiseitherapathP(vi,vj)orapathP(vi,vj).45MainIndexContentsAdjacencyMatrixAnmbymmatrix,calledanadjacencymatrix,identifiestheedges.Anentryinrowiandcolumnjcorrespond
5、stotheedgee=(v,,vj).Itsvalueistheweightoftheedge,or-1iftheedgedoesnotexist.56MainIndexContentsAdjacencySet67MainIndexContentsvertexInfoObjectAvertexInfoobjectconsistsofsevendatamembers.Thefirsttwomembers,calledvtxMapLocandedges,identifythevertexinthemapan
6、ditsadjacencyset.78MainIndexContentsVertexMapandVectorvInfoTostoretheverticesinagraph,weprovideamapcontainer,calledvtxMap,whereavertexnameisthekeyoftypeT.TheintfieldofamapobjectisanindexintoavectorofvertexInfoobjects,calledvInfo.Thesizeofthevectori
7、sinitiallythenumberofverticesinthegraph,andthereisa1-1correspondencebetweenanentryinthemapandavertexInfoentryinthevector8VtxMapandVinfoExample9Breadth-FirstSearchAlgorithm10Breadth-FirstSearch…(Cont.)11dfs()12StrongComponentsAstronglyconnectedcomponentofa
8、graphGisamaximalsetofverticesSCinGthataremutuallyaccessible.13GraphGandItsTransposeGTThetransposehasthesamesetofverticesVasgraphGbutanewedgesetETconsistingoftheedgesofGbutwiththeoppositedirection.14Shortest-PathExam
