资源描述：
《算法分析与设计2005春.课件.第07讲6 清华大学：算法分析与设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、内容提要第七讲图的基本算法RepresentationofgraphicsBreadth-firstsearchDepth-firstsearch清华大学Topologicalsort宋斌恒Stronglyconnectedcomponents清华大学宋斌恒1清华大学宋斌恒2图的应用背景Representationofgraphs可以利用图描述的经典问题有Definitionofagraph:Petri－NetG=(V,E)whereVisasetofvertices,EisWorkFlowanothersetcallEdgesisasubsetof{(u,
2、v):u城市与连接城市的道路andviselementofV}区域与隔离区域间的分界线Conceptsofgraphs:人与人之间的认识关系Densegraph:if
3、E
4、iscloseto
5、V
6、2.任何二元关系都可以用图来表示Sparsegraph:Ifitisnotdense基本算法的应用许多与图有关的算法需要做一种搜索清华大学宋斌恒3清华大学宋斌恒41225/24/010011235/0101001534/10111000010324/0101065/000011253/011012/0100001101054412/5464/000100/00000
7、0Figure22.1Tworepresentationsofanundirectedgraph.(a)AnundirectedgraphGhavingfiveverticesandsevenedges.(b)Anadjacency-listrepresentationofG.(c)Theadjacency-matrixrepresentationofG.清华大学宋斌恒5清华大学宋斌恒61DatastructureofAdjacency-listAdjacency-listrepresentationrepresentationLetGbeagraph,fo
8、ranyu∈V,weAsetofvertexobjectsdenoteAdj[u]={v:(u,v)∈E},callthelistVertexobjectcontainsonevertexu,andaofalladjacencyverticesofu.setofverticesAdj[u],whichcontainsallitsIngeneralelementinAdj[u]isunorderedadjacencyverticesofu.Inanundirectedgraph?UsingwhatdatastructuretorepresentaSum(Adj
9、[u],forallu∈V)=2
10、E
11、setforthevertexobjectsButinadirectedgraph?UsingwhatdatastructuretorepresentaSum(Adj[u],forallu∈V)=1
12、E
13、setforAdj[u]清华大学宋斌恒7清华大学宋斌恒8Adjacency-listrepresentationforWeightedGraphWeightedGraphicsWecanassignvaluetotheedgesofaWereconstructthesetAdj[u]asgraph,thenwecalls
14、uchagraphisaAdj[u]={(v,r):v∈V,r∈R}whereRistheweightedgraph.spaceofrealnumberorgenerallyanyobjectspaceClassically,aweightedgraphhasitsedgevaluebelongtoR,butwecanextendittovaluesfromanyparticularspaces,say,spacescontainingcomplexobjectsw:EÆRistheweightfunction清华大学宋斌恒9清华大学宋斌恒10Moregen
15、eralgraphicsMatrixrepresentationWecanalsoassignvaluestotheverticesA=(aij)n*n.ofagraph,thenitneedsamoregenerala=1if(i,j)∈E,0else.ijrepresentationtopresentsuchagraphItiscalledtheadjacencymatrix!GiveanAdjacency-listlikedatastructure?Howtopresentitforthecaseofweightedtorepresentsuchagr
16、aph.graph??Formoregeneralc
