2006 算法设计qiu-lec10

《2006 算法设计qiu-lec10》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图(Graphs)•Applicationsthatinvolvenotonlyasetofitems,butalsothe算法设计与分析connectionsbetweenthem(物体及物体之间的连接关系)AlgorithmsDesign&Analysis第十讲：图的算法ComputernetworksMaps(地图)Schedules(日程表)(计算机网络)华中科技大学软件学院邱德红主讲2005年4月Hypertext(超文本)Circuits(电路板)12图的背景知识(Graphs–Background)图的其它类型(OtherT

2、ypesofGraphs)Graphs=asetofnodes(vertices)withedges•Agraphisconnectedifthereisapath1212(links)betweenthem.(节点+边)betweeneverytwovertices(如果任何两个顶点之间存在一个通路,则称图是连Notations:(表示方法)接的)3434•G=(V,E)–graph(图)ConnectedNotconnected•V=setofvertices⎜V⎜=n(节点和节点数目)•E=setofedges⎜E⎜=m(边和边的数

3、目)•AbipartitegraphisanundirectedgraphG=(V,E)inwhichV=V1+V212121212andthereareedgesonlybetween9verticesinVandV(二分图：无向4812343434图，由V1和V2组成，只在V1和V2之间的367顶点存在边)4DirectedUndirectedAcyclicGraph(有向图)Graph(无向图)Graph(无回路图)34邻接表特性(PropertiesofAdjacency-图的表示方法（GraphRepresentation）Li

4、stRepresentation)•AdjacencylistrepresentationofG=(V,E)(邻接表)•Sumofthelengthsofalltheadjacency–Anarrayof⎜V⎜lists,oneforeachvertexinV(顺序存储的顶点表)12–EachlistAdj[u]containsalltheverticesvsuchthatthereisanedgebetweenuandv(边表:一个顶点的边表的每个表目对应与该顶lists（邻接表长度的和→边的数目）点相关联的一条边)34•Adj[u]c

5、ontainstheverticesadjacenttou(inarbitraryorder)(顺序无关)–Directedgraph:(有向图：边出现一次)–Canbeusedforbothdirectedandundirectedgraphs(适合有向或无Directedgraph向图)•Edge(u,v)appearsonlyonceinu’slist⎜E⎜125/12–Undirectedgraph:(无向图：边出现两次)1221534/33324•uandvappearineachother’sadjacencylists:54

6、544253/edge(u,v)appearstwice2⎜E⎜5412UndirectedgraphUndirectedgraph561邻接表特性（PropertiesofAdjacency-图的表示方法(GraphRepresentation)ListRepresentation）•Memoryrequired(空间需求)•AdjacencymatrixrepresentationofG=(V,E)(相邻矩阵)–Θ(V+E)12–Assumeverticesarenumbered1,2,…⎜V⎜(顶点序号)•Preferredwhen

7、(适合⎜E⎜<<⎜V⎜2)3–TherepresentationconsistsofamatrixA⎜V⎜x⎜V⎜:–thegraphissparse:⎜E⎜<<⎜V⎜254–aij=1if(i,j)∈E(元素值的确定)•Disadvantage(缺陷)0otherwise–noquickwaytodeterminewhetherthereisanUndirectedgraphedgebetweennodeuandv(不容易判断顶点u和v12345之间是否存在边)1212101001Forundirected•Timetolistallv

8、erticesadjacenttou:(罗列与u3211011graphsmatrixA邻接顶点的时间开销)34300011issymmetric:–Θ(degree(u))54•Timeto