北京大学计算机系数据结构讲义北京大学计算机系数据结...

《北京大学计算机系数据结构讲义北京大学计算机系数据结...》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章第七章图图张张铭铭数据库与信息系统教研室数据库与信息系统教研室北京大学计算机系数据结构讲义图图©图被广泛地用于模拟真实事件或抽象问题。在语言学、逻辑学、物理、化学、电讯工程、计算机、数学等学科领域得到了广泛的应用。©下图为一个网络连接图例85323265381223631114721451§7.1基本概念和术语©数据的逻辑结构可以表示为二元组B=(K,R)，，在，在数据结构中研究一个关系的情况，R={r}。ò如果关系r不限制结点之间的关系，任意一对结点间都允许有一个关系(边)，这样的结构就是图。ò图是最基本的数据结构，树和线性表可看作受限图。©图可

2、用G=(V,E)来表示，结点在图中称为顶点，顶点的非空有穷集合记为V；；顶点；顶点(结点)的偶对称为边，边的集合记为E，E内的每条边都是V中某一对顶点的连接。顶点总数计为

3、

4、V

5、

6、V

7、，，边的，边的总数记为

8、

9、E

10、

11、E

12、，

13、E

14、的取值范围是0到Ο(

15、(

16、V

17、(

18、V

19、2)。术语（续术语（续1术语（续11）1）©若图中的边限定为从一个顶点指向另一个顶点，则称此图为有向图。ò有向图中的顶点偶对用尖括号来表示，<和<代表不同的边。1221©若图中的边无方向性，则称之为无向图。ò无向图中的顶点偶对用圆括号来表示，((v(v,v)和((v

20、(v,v)代表同一条的边。1221术语（续2）©边数较少的图称为稀疏图边数较少的图称为稀疏图，边数较少的图称为稀疏图，，边数较多的图，边数较多的图称为密集图称为密集图，称为密集图，，包括所有可能边的图称为完全，包括所有可能边的图称为完全图©有向图的完全图有n·(n(n-(n-1)条边。无向图的完全图有C2==n=n·(n(n-(n-1)/2条边。n©一条边所连接的两个顶点是相邻的一条边所连接的两个顶点是相邻的，一条边所连接的两个顶点是相邻的，，称为，称为邻接点邻接点。邻接点。。连接一对邻接点。连接一对邻接点u、v的边被称为与顶点u、v相关联的边，记作((

21、u(u，v)。术语（续3）©一个顶点v的度是与该顶点相关联的边的数目，记为TD(v)©若G是一个有向图，则把以顶点v为终点的边数称为顶点v的入度的入度，的入度，，记为，记为ID(v)©把以顶点v为起点的边数称为顶点v的出度度，度，，记为，记为OD(v)©顶点v的度数为TD(v)=ID(v)+OD(v)术语（续4）©设图G(可以为有向或无向图)共有n个顶点，e条边，若顶点v的度数为TD(v)ii，，则，则1n−1eT=∑D()vi2i=0ò因为一条边关联两个顶点，而且使得这两个顶点的度数分别增加个顶点的度数分别增加1个顶点的度数分别增加11。因此顶点的度1

22、。因此顶点的度数之和就是边的两倍。术语（续5）©路径路径：路径：：从：从vixix-ix-1到vix(1≤1≤x≤k)的边都存在，则称顶点序列v,v,…，v构成一条长i0i1ik度为k的路径的路径。的路径。©简单路径：路径上各顶点均不同©路径长度：路径所包含的边的条数。©回路：一条路径将某个顶点(如v1)连接到它本身，且其长度大于等于3。©简单回路：构成回路的是简单路径，其中只有首尾两顶点相同只有首尾两顶点相同。只有首尾两顶点相同。术语（续6）©不带回路的图称为无环图。©不带回路的有向图则称为有向无环图(directedacyclicgraph，，简称为

23、，简称为DAG图)©有根图：有根图：一个有向图中，若从某个顶点有根图：一个有向图中，若从某个顶点vx出发，可以找到路径到达图中其它所有顶点。这个顶点v就是图的根。x©子图子图：子图：：由图：由图G中选出其顶点集的一个子集Vs及与V中顶点相关联的一些边所构成的图。s术语（续7）©连通图：一个无向图中任一顶点到其它任意顶点都至少存在一条路径意顶点都至少存在一条路径。意顶点都至少存在一条路径。©连通分量：无向图的极大连通子图连通分量：无向图的极大连通子图。连通分量：无向图的极大连通子图。©强连通图：在有向图G中，如果对于任意两个顶点v和v(v≠v)，，都同时存

24、在从，都同时存在从v到ijijiv的(有向)路径和从v到v的(有向)路径jji©强连通分量：有向图的极大强连通子图强连通分量：有向图的极大强连通子图。强连通分量：有向图的极大强连通子图。有三个连通分量的无向图V0V1V2V6V9V4V3V5V7V8连通的无向图及其强连通分量连通的无向图及其强连通分量V0V1V2V1V2V0V4V4V3V5V3V5图G2图G2的三个强连通分量术语（续8）©每条边都可能附有其值或权，这样的图称为带权图称为带权图。称为带权图。。带权的连通图称为网络，。带权的连通图称为网络，如下图所示。©V0V0V1V1V25V25779269

25、2611V41V32V5V412V3V5(a)图G3(b)图G4术语（续9）©一