数据结构 教学课件 作者 宗大华 陈吉人 07图.ppt

《数据结构 教学课件 作者 宗大华 陈吉人 07图.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第7章图7.1图的概述7.2图的存储结构7.3图的遍历7.4生成树与最小生成树7.5最短路径7.6拓扑排序图是一种比树更为复杂的非线性结构。在图状结构中，任意两个结点之间都可能具有邻接关系，即在图的数据元素之间存在多对多的关系。本章主要介绍以下几个方面的内容：图的定义及常用术语；图的各种存储结构；图的遍历；构造最小生成树的算法；求最短路径的算法；拓扑排序及其算法。7.1图的概述在讲述图时，习惯把数据元素统称为是顶点。“图”是图状结构的简称，它由一个非空的顶点集合V和一个描述顶点之间邻接关系的边集合E组成，E中每条边连接的两个顶点都必须属于集合V。于是，一个

2、图可以记为：G=（V，E）对于一个图G来说，边的集合E可以是空的。7.1.1图的定义若vi、vj是V集合中的两个顶点，且有边连接，那么就用记号（vi，vj）表示顶点vi到顶点vj之间的边。通常，边是没有方向的，即若图G中有边（vi，vj），那么也可以说有边（vj，vi）。当图中的边不带有方向时，称该图为“无向图”。若图中的边是有向的，这样的图被称为“有向图”。在有向图中，有边（vi，vj），并不意味着也有边（vj，vi）。常称有向图的边为“弧”，把有向图中从顶点vi到顶点vj的弧记为，而把从顶点vj到顶点vi的弧记为，这是两条不同的弧。由于

3、有向图的弧是有方向的，因此常称弧的起始顶点为“弧尾”，弧的终止顶点为“弧头”。图7-1无向图和有向图1．顶点的度、入度、出度7.1.2有关图的常用术语无向图中，若顶点vi和vj之间有一条边（vi，vj）存在，则表明顶点vi和vj互为邻接点，简称vi与vj相邻接。所谓顶点vi的“度”，是指与它相邻接的顶点的个数，记为D(vi)。在有向图中，以顶点vi为弧尾的弧的个数，称为顶点vi的“出度”，记为OD(vi)；以顶点vi为弧头的弧的个数，称为顶点vi的“入度”，记为ID(vi)。这时，一个顶点vi的度是指它的入度与出度之和，即：D(vi)=ID(vi)+OD(vi)。在无

4、向图G中，所谓从顶点vi到顶点vj的一条“路径”，是指在顶点vi与顶点vj之间存在有一个边的序列：（vi,vi1），（vi1,vi2），…，（vim,vj）其中顶点vi、vi1、vi2、…、vim、vj属于G的顶点集合V，边（vi,vi1）、（vi1,vi2）、…、（vim,vj）属于G的边的集合E。2．路径、路径长度对于有向图G，所谓从顶点vi到顶点vj的一条“路径”，是指在顶点vi与顶点vj之间存在有一个弧的序列：，，…，其中顶点vi、vi1、vi2、…、vim、vj属于G的顶点集合V，弧、

5、,vi2>、…、属于G的弧的集合E。所谓顶点vi到顶点vj的路径“长度”，是指在这条路径上拥有的边的个数。若在一条路径上出现的顶点都不同，那么这条路径称为“简单路径”；若一条路径的第一个顶点和最后一个顶点相同，其他顶点不重复出现，那么这条路径称为“简单回路”；若一条路径的第一个顶点和最后一个顶点相同，那么这条路径称为“回路”，有时也称作“环”。3．简单路径、简单回路、回路若一个有n个顶点的无向图，拥有n(n−1)/2条边，那么就称该图为“无向完全图”。对于一个无向完全图来说，它的每个不同顶点对之间，都存在有一条边。若一个有n个顶点的有向图，拥有n(n−

6、1)条弧，那么就称该图为“有向完全图”。对于一个有向完全图来说，它的每个不同顶点对之间，都存在有两条弧。4．无向完全图、有向完全图图7-2（a）所示为一个无向完全图，由于它有4个顶点，所以它有4(4−1)/2=6条边；图7-2（b）所示为一个有向完全图，由于它有4个顶点，所以它有4(4−1)=12条弧。图7-2无向、有向完全图无论是无向图还是有向图，图中的每一条边或弧都与两个顶点有关。因此，在图的顶点数n、边数e以及各顶点的度D(vi)（1≤i≤n）三者之间，有如下的关系存在：已知两个图G=（V，E），G′=（V′，E′）。若有V′是V的子集，E′是E的子集，且E

7、′中的边（或弧）都依附于V′中的顶点，那么就称G′是G的一个“子图”。5．子图图7-3子图示例连通、连通图、连通分量都是关于无向图的概念。在无向图中，若从顶点vi到顶点vj之间有路径存在，则称vi与vj是“连通”的。如果无向图G中任意一对顶点之间都是连通的，则称该图G为“连通图”，否则是非连通图。6．连通、连通图、连通分量在无向图G中，尽可能多地从集合V及E里收集顶点和边，使它们成为该图的一个极大的连通子图，这个子图就被称为是无向图G的一个“连通分量”。图7-4连通图、非连通图、连通分量有时，可以给图的边或弧依附上某种数值，这种与图的边或弧相关的数值