资源描述：
《数据结构 宗大华 宗杰 黄芳 数据结构 大本课件-7》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第7章图7.17.27.3本章讲述内容：图的概述图的存储结构图的遍历生成树与最小生成树7.4最短路径7.5拓扑排序与关键路径7.6图是一种比树更为复杂一些的非线性结构。在图状结构中，任意两个结点之间都可能具有邻接关系，也就是在图的数据元素之间存在多对多的关系。前面讲述的各种数据结构，都可看作是图的特例。从某种意义上说，图应该是一种最基本的数据结构。7.1图的概述7.1.1图的定义..在图中，习惯把数据元素统称为是“顶点”。.“图”是图状结构的简称，它由一个非空的顶点集合V和一个描述顶点间邻接关系的边集合E组成，E中每条边连接的两个顶点都必须属于集合V。于是，一个图可记为：G=(V，E)
2、1.图的定义对于图G，边的集合E可以是空的。如果边集合E为空(即E={Ф})，那么表示图G只有顶点而没有边。2.图的有关概念..若vi、vj是V集合中的两个顶点，且有边连接，那么就用记号(vi，vj)表示顶点vi到顶点vj之间的边。.通常，边没有方向。即若图G中有边(vi，vj)，那么也有边(vj，vi)。当图中的边不带方向时，称该图为“无向图”。在无向图中，边(vi，vj)与(vj，vi)等价，视为是一条边。.若图中的边是有向的，则被称为“有向图”。在有向图中，有边(vi，vj)，并不意味着也有边(vj，vi)。即对于有向图，(vi，vj)和(vj，vi)是两条不同的边。为区别起见，
3、常称有向图的边为“弧”，把有向图中从顶点vi到顶点vj的弧记为，而把从顶点vj到顶点vi的弧记为，这是两条不同的弧。由于有向图的弧是有方向的，因此称弧的起始顶点为“弧尾”，终止顶点为“弧头”。.例7-1：通过图认识无向图和有向图。V1V2V3V4V5V1V2V3V4V5.如图所示为一个无向图，该图的组成如下：V={v1，v2，v3，v4，v5}E={(v1,v2),(v1,v3),(v1,v4),(v1,v5),(v2,v4),(v3,v4),(v3,v5),(v4,v5)}，比如，由于图中有边(v1,v2)(也就是有边(v2,v1))，表示顶点v1和顶点v
4、2(或顶点v2和顶点v1)之间存在有邻接关系。如图所示为一个有向图，该图的组成如下：V={v1，v2，v3，v4，v5}E={,,,,,,}.比如，由于有弧，表示顶点v1到顶点v2有邻接关系；由于有弧，表示顶点v2到顶点v1有邻接关系。又比如，由于有弧，表示顶点v3到顶点v1有邻接关系；因为顶点v1到顶点v3之间没有弧，故顶点v1到顶点v3之间不存在邻接关系。..比如在有向图里，由于弧和都以顶点v1为弧头，所以顶点v1的
5、入度ID(v1)=2；由于弧以顶点v1为弧尾，所以顶点v1的出度OD(v1)=1；于是，顶点v1的度为：D(v1)=ID(v1)+OD(v1)=2+1=3比如在无向图里，顶点v1的度是4，即有D(v1)=4，因为它与4个顶点(v2、v3、v4、v5)相邻接；顶点v2的度是2，即有D(v2)=2，因为它只与顶点v1、v4相邻接。7.1.2有关图的常用术语1.顶点的度、入度、出度在无向图中，若顶点vi和vj之间有一条边(vi，vj)存在，那么表明顶点vi和vj互为邻接点，简称vi与vj相邻接。所谓顶点vi的“度”，是指与它相邻接的顶点的个数，记为D(vi)。..V1V2V3V
6、4V5V1V2V3V4V5.在有向图中，以顶点vi为弧尾的弧的个数，称为顶点vi的“出度”，记为OD(vi)；以顶点vi为弧头的弧的个数，称为顶点vi的“入度”，记为ID(vi)。这时，一个顶点vi的度是指它的入度与出度之和，即：D(vi)=ID(vi)+OD(vi)。.2.路径、路径长度.在无向图G中，所谓从顶点vi到顶点vj的一条“路径”，是指在顶点vi与顶点vj之间存在有一个边的序列：(vi,vi1),(vi1,vi2),…,(vim,vj)其中顶点vi、vi1、vi2、…、vim、vj都属于无向图G的顶点集合V，边(vi,vi1)、(vi1,vi2)、…、(vim,vj)都属于
7、无向图G的边的集合E。.在有向图G里，所谓从顶点vi到顶点vj的一条“路径”，是指在顶点vi与顶点vj之间存在有一个弧的序列：，，…，其中顶点vi、vi1、vi2、…、vim、vj都属于有向图G的顶点集合V，弧、、…、都属于有向图G的弧的集合E。.若从顶点v1开始，中间经过顶点v2、v3、v4到顶点v5有一条路径，那么就记为：v1→v2→v3→v
