欢迎来到天天文库
浏览记录
ID:33759849
大小:296.64 KB
页数:9页
时间:2019-03-01
《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
此文档下载收益归作者所有