东南大学计算机学院方效林

《东南大学计算机学院方效林》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、东南大学计算机学院方效林本课件借鉴了清华大学殷人昆老师和哈尔滨工业大学张岩老师的课件第七章图本章主要内容图的基本概念图的存储表示图的遍历与连通性最小生成树最短路径2图的基本概念定义图是由顶点及顶点之间的关系集合组成的数据结构Graph=(V,E)V是顶点的有穷非空集，V={x

2、x∈某个对象}E是顶点之间关系，称为边(edge)的有穷非穷集，E={(x,y)

3、x,y∈V}3图的基本概念有向图与无向图有向图中，顶点对(x,y)是有序的无向图中，顶点对(x,y)是无序的完全图n个顶点的无向图有n(n-1)/2条边,该图为完全图n个顶点的有向图有n(n-1)条边,该图为完全有向图421302140

4、完全无向图867365无向图(自由树)120有向图完全有向图图的基本概念邻接顶点(u,v)是E中的一条边，则称u与v互为邻接顶点子图设有两个图G＝(V,E)和G’＝(V’,E’)。若V’V且E’E,则称G’是G的子图权：边附带的权重，称这样的图称为带权图521301302132130子图图的基本概念顶点v的度与v为端点的边条数，记作D(v)入度：有向图中,以v为终点的边的条数,记作ID(v)出度：有向图中,以v为始点的边的条数,记作OD(v)有向图中v的度为入度与出度的和路径图G＝(V,E)中,从顶点vi出发,沿一些边经过一些顶点vp1,vp2,…,vpm，到达顶点vj。则称顶点序列(

5、vivp1vp2...vpmvj)为从顶点vi到顶点vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、...、(vpm,vj)应是属于E的边。6图的基本概念路径长度非带权图的路径长度是指此路径上边的条数带权图的路径长度是指路径上各边的权之和简单路径路径上各顶点v1,v2,...,vm均不互相重复回路路径上第一个顶点v1与最后一个顶点vm重合7图的基本概念连通图与连通分量无向图中,从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。若图中任意一对顶点都是连通的,则此图是连通图非连通图的极大连通子图叫连通分量821304连通图521304非连通图(有2个连通分量)5图的基本概念强

6、连通图与强连通分量在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图非强连通图的极大强连通子图叫做强连通分量生成树一个连通图的生成树是其极小连通子图，在n个顶点的情形下，有n-1条边。9图的存储表示邻接矩阵一个有n个顶点的图G=(V,E)，图的邻接矩阵是一个二维数组A.edge[n][n]10120有向图的邻接矩阵可能不对称2130无向图的邻接矩阵是对称的图的存储表示邻接矩阵网络(带权图)的邻接矩阵11321086395214图的存储表示邻接表无向图的邻接表12DBCA12003CBDA12130datalinkdestlinkd

7、estlinkdest保存的是邻接顶点的下标顶点数组链接结点图的存储表示邻接表有向图的邻接表和逆邻接表13102CBA210datalinkdestlinkBCA102CBA210datalinkdestlinkdestlink邻接表(出边表)逆邻接表(入边表)图的存储表示网络(带权图)的邻接表14邻接表(出边表)CDBA86395214CBDA2130datalinkcostlink3063221142destcostlinkdest935182图的遍历从给定顶点出发，沿某些边遍历图中所有顶点一次且仅一次使用辅助数组visited[]标识顶点是否被访问过visited

8、[]初始为0访问过后标识为115图的遍历遍历方式深度优先遍历DFS(DepthFirstSearch)广度优先遍历BFS(BreadthFirstSearch)16图的遍历遍历方式深度优先遍历DFS(DepthFirstSearch)从顶点v1出发，访问任一未被访问的邻接顶点v2;再从顶点v2出发，访问任一未被访问的邻接顶点v3;再从顶点v3出发，…，如此进行下去，直到所有邻接顶点都被访问过为止退回一步到刚被访问的顶点，看是否有未被访问的邻接顶点。若有，则继续访问否则，再退回一步直到所有顶点都被访问17图的遍历遍历方式深度优先遍历DFS(DepthFirstSearch)18前进回退深度优

9、先搜索过程深度优先生成树ABEDCGFHI123456789ABEDCGFHI123456789图的遍历遍历方式广度优先遍历BFS(BreadthFirstSearch)从起始顶点v出发，依次访问v的未被访问的邻接顶点w1,w2,…,wm顺序访问w1,w2,…,wm的所有未被访问的邻接顶点,以此类推，直到所有顶点都被访问19图的遍历遍历方式广度优先遍历BFS(BreadthFirstSearch)20广度优先搜索过程广度