资源描述：
《麻省理工大学算法导论lecture16》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、IntroductiontoAlgorithms6.046J/18.401J/SMA5503Lecture16Prof.CharlesE.LeisersonGraphs(review)Definition.Adirectedgraph(digraph)G=(V,E)isanorderedpairconsistingof•asetVofvertices(singular:vertex),•asetE⊆V×Vofedges.InanundirectedgraphG=(V,E),theedgesetEcons
2、istsofunorderedpairsofvertices.Ineithercase,wehave
3、E
4、=O(V2).Moreover,ifGisconnected,then
5、E
6、≥
7、V
8、–1,whichimpliesthatlg
9、E
10、=Θ(lgV).(ReviewCLRS,AppendixB.)©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay27L16.2Adjacency-matrixrepresentationTheadjacencymat
11、rixofagraphG=(V,E),whereV={1,2,…,n},isthematrixA[1..n,1..n]givenby1if(i,j)∈E,A[i,j]=0if(i,j)∉E.A1234221110110Θ(V2)storage20010⇒dense334430000representation.40010©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay27L16.3Adjacency-listrepresentationAnadja
12、cencylistofavertexv∈VisthelistAdj[v]ofverticesadjacenttov.Adj[1]={2,3}2211Adj[2]={3}Adj[3]={}3344Adj[4]={3}Forundirectedgraphs,
13、Adj[v]
14、=degree(v).Fordigraphs,
15、Adj[v]
16、=out-degree(v).HandshakingLemma:∑=2
17、E
18、forundirectedv∈Vgraphs⇒adjacencylistsuseΘ(V+E)stor
19、age—asparserepresentation(foreithertypeofgraph).©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay27L16.4MinimumspanningtreesInput:Aconnected,undirectedgraphG=(V,E)withweightfunctionw:E→R.•Forsimplicity,assumethatalledgeweightsaredistinct.(CLRScoversth
20、egeneralcase.)Output:AspanningtreeT—atreethatconnectsallvertices—ofminimumweight:w(T)=∑w(u,v).(u,v)∈T©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay27L16.5ExampleofMST61259147815310©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay27L16.6Optimalsu
21、bstructureMSTT:uT2(OtheredgesofGT1arenotshown.)vRemoveanyedge(u,v)∈T..Then,TispartitionedintotwosubtreesTandT.12Theorem.ThesubtreeTisanMSTofG=(V,E),1111thesubgraphofGinducedbytheverticesofT:1V=verticesofT,11E={(x,y)∈E:x,y∈V}.11SimilarlyforT.2©2001byCharl
22、esE.LeisersonIntroductiontoAlgorithmsDay27L16.7ProofofoptimalsubstructureProof.Cutandpaste:w(T)=w(u,v)+w(T)+w(T).12IfT′werealower-weightspanningtreethanTfor11G,thenT′={(u,v)}∪T′∪Twouldbea112lower-weightspanningtreethanTfor
