《数据结构教学作者主编马世霞第6章节图课件》由会员分享，可在线阅读，更多相关《数据结构教学作者主编马世霞第6章节图课件（64页珍藏版）》请在金锄头文库上搜索。
1、第六章 图,本章要点,图的定义和术语 一般排序算法的设计与实现 排序算法的效率分析,6.1 图的基本概念,图的定义：图(Graph)是由顶点集合和一个描述顶点之间关系边（弧）的集合组成的一种数据结构，其形式化定义为： G（V，E） 其中 V = x | x 某个数据对象 是顶点的有穷非空集合； E1 = (x, y) | x, y V 或 E2 = | x, y V 其中， E1是边(edge)的集合，此时的图称为无向图。 E2 表示弧的集合，这样的图称为有向图。,无向图G1的示例：集合Vv1,v2,v3,v4,v5； 集合E(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v
2、3,v5),(v2,v5),（1）无向图 在一个图中，如果任意两个顶点构成的无序偶对（vi, vj）E，即顶点之间的连线是没有方向的，则称该图为无向图。 如图6-1所示是一个无向图G1。 （2）有向图 在一个图中，如果任意两个顶点构成的有序偶对E，即顶点之间的连线是有方向的，则称该图为有向图。 如图6-2所示是一个有向图G2： G2=(V2, E2) V2=v1,v2,v3,v4 E2=,图的相关术语：,（3）顶点、边、弧、弧头、弧尾 图中，数据元素vi称为顶点； 在无向图中， (vi, vj)称为边； 在有向图中， 为弧。 边用顶点的无序偶对（vi, vj）来表示，称顶点vi和顶点vj互为邻
3、接点，边（vi, vj）依附于顶点vi与顶点vj； 弧用顶点的有序偶对来表示，有序偶对的第1个结点vi被称为始点（或弧尾），在图中就是不带箭头的一端；有序偶对的第2个结点vj被称为终点（或弧头），在图中就是带箭头的一端。,（4）顶点的度、入度、出度 顶点的度（degree）是指依附于某顶点v的边数或弧数，通常记为TD (v)。在有向图中，要区别顶点的入度与出度的概念。 顶点v的入度是指以顶点为终点的弧的数目。记为ID (v)； 顶点v出度是指以顶点v为始点的弧的数目，记为OD (v)。有： 顶点的度(TD)=出度(OD)+入度(ID) 可以证明，对于具有n个顶点、e条边（弧）的图，顶点vi的度
4、TD (vi)与顶点的个数以及边的数目满足关系：,（5）路径、路径长度 顶点vp到顶点vq之间的路径（path）是指顶点序列vp,vi1,vi2, , vim,vq.。其中，（vp,vi1），(vi1,vi2)，,(vim,.vq)分别为图中的边。路径上边的数目称为路径长度。 图6-1所示的无向图G1中，v1v4v3v5是从顶点v1 到顶点v5 的一条路径，路径长度为3。 （6）简单路径、简单回路 简单路径：若路径上各顶点 v1,v2,.,vm 均不互相重复, 则称这样的路径为简单路径。图6-1所示的无向图G1中，v1v4v3v5，是简单路径。 简单回路：若路径上第一个顶点 v1 与最后一个顶
5、点vm 重合, 则称这样的路径为回路或环。在一个回路中，若除第一个与最后一个顶点外，其余顶点不重复出现的回路称为简单回路或简单环(如图6-2中的v1v3v4v1。,（7）无向完全图 在无向图中，如果任意两顶点都有一条边，则称该图为无向完全图。可以证明，在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。 图6-3是无向完全图，边数n=4(4-1)/2=6 ，,图6-3 无向完全图,（8）有向完全图 在有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。 在一个含有n个顶点的有向完全图中，有n(n-1)条边。 如图6-5有向完全图，边数=3(3-1)=6,图6
6、-5 有向完全图,（9）稠密图、稀疏图 若一个图接近完全图，称为稠密图；称边数很少的图为稀疏图。 （10）子图。对于图G=（V，E），G=（V，E），若存在V是V的子集 ，E是E的子集 ，则称图G是G的一个子图。图6-6所示子图部分。,图6-6 子图实例,（11）边的权、网图 与边有关的数据信息称为权。在实际应用中，权值可以有某种含义。比如，在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或者等级；对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间等等。边上带权的图称为网图或网络。如图6-7所示，就是一个无向网图。如果边是有方向的带权图，则就是一个有
7、向网图。,（12）连通的、连通图、连通分量 在无向图中，如果从一个顶点vi到另一个顶点vj(ij)有路径，则称顶点vi和vj是连通的。如果图中任意两顶点都是连通的，则称该图是连通图。无向图的极大连通子图称为连通分量。图6-8 (a)中有两个连通分量，如图6-8 (b)所示。,（13）强连通图、强连通分量 对于有向图来说，若图中任意一对顶点vi 和vj(ij)均有从一个顶点vi到另一个顶点vj有路径，也有从vj到vi的路径，则称该有向图 是强连通图。有向图的极大强连通子图称为强连通分量。 图6-2中有两个强连通分量，分别是v1,v3,v4和v2，如图6-6所示。,（14）生成树 生成树是无向连通
8、图的一个极小连通子图。如果无向图有n个顶点，那么它必定包含且仅包含G的n-1条边。在生成树中添加任意1条属于原图中的边必定会产生回路，因为新添加的边使其所依附的两个顶点之间有了第2条路径。若生成树中减少任意一条边，则必然成为非连通的。但有n个顶点和n-1条边的图并非一不定期连通，不一定是生成树。 （15）生成森林 对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。,6.2 图的存储表示,图是多对多的结构，比线性结构、树结构复杂，其存储结构也要复杂些。图的存储结构至少要保存两类信息： （1）顶点的信息 （2）顶点间的关系 注意：顶点的编号，为了使图的存储结构与图一一对应，在讨论
9、图的存储结构时，首先要给图的所有顶点编号。,6.2.1 邻接矩阵,图是多对多的结构，比线性结构、树结构复杂，其存储结构也要复杂些。图的存储结构至少要保存两类信息： （1）顶点的信息 （2）顶点间的关系,6.2.1 邻接矩阵,邻接矩阵的存储结构，就是用一维数组存储图中顶点的信息，用矩阵表示图中各顶点之间的邻接关系。 假设图G（V，E）有n个确定的顶点，即Vv0,v1,vn-1,则表示G中各顶点相邻关系为一个nn的矩阵，矩阵的元素为：,若G是网，则邻接矩阵可定义为：,其中，wij表示边(vi,vj)或上的权值；表示一个计算机允许的、大于所有边上权值的数。用邻接矩阵表示法表示图如图6-10所示，用邻
10、接矩阵表示法表示网图如图6-11所示。,图6-10 无向图的邻接矩阵表示,图6-11 一个网的邻接矩阵表示,注意：图的邻接矩阵存储方法具有以下特点： （1）无向图的邻接矩阵是对称的，同一条边表示了两次； （2）顶点v的度： 在无向图中等于二维数组对应行（或列）中1的个数； 在有向图中：顶点 i 的出度=第 i 行 1 的个数；顶点 j 的入度=第 j 列 1 的个数。如图6-12所示。 （3）判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为1；,图6-12 V1的入度、出度,在用邻接矩阵存储图时，除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外，还需用一个一维数组来存储顶点信
11、息，另外还有图的顶点数和边数。故可将其形式描述如下：,typedef struct char vexsMaxVerNum; /*顶点表*/ int edgesMaxVerNumMaxVerNum; /*邻接矩阵，即边表*/ int n,e; /*顶点数和边数*/ Mgraph; /*Maragh是以邻接矩阵存储的图类型*/,【例6-1】如图6-13所示，用二维数组表示如下: connection2=1,2,2,3,2,5,3,5,3,4,1,4; 编程实现邻接矩阵,6.2.2 邻接表,对于顶点数多而边数少的图，用nn方阵的存储结构极大地浪费存储空间，因此可考虑另一种存储结构，即邻接表。它对于无
12、向图和有向图都适用。就是对于图中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有顶点的邻接表表头放到数组中，就构成了图的邻接表。在邻接表表示中有两种结点结构，如图所示。,在邻接表中，一种是对图中每个顶点建立一个顶点数据表，可以采用顺序存储结构实现，表头结点由顶点域（data）和指向第一条邻接边的指针域（firstedge）构成，另一种是边链表，它由邻接点域(adjvex)和指向下一条邻接边的指针域(next)构成。 图6-16给出无向图6-10对应的邻接表表示。,图6-16 图的邻接表表示,对于网的边链表需再增设一个存储边上信息（如权值等）的
13、域（info），网的边链表结构如图6-17所示。图6-18给出网络 (带权图)的邻接表表示。,图6-17 网的边链表结构,图6-18 网 (带权图) 的邻接表,为了便于确定顶点的入度或以顶点vi为头的弧，可以建立一个有向图的逆邻接表，即对每个顶点vi 建立一个以vi为弧头的链表。例如下图所示为有向图的邻接表和逆邻接表。,(a) 邻接表,6.3 图的遍历,图的遍历是指从图中的某一顶点出发，对图中的所有顶点访问一次且只访问一次，这一过程就叫做图的遍历。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。,由于图结构本身的复杂性，所以图的遍历操作也较复杂， 主要表现在以下四个方
14、面： 在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。, 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。 在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。 在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。,6.3.1 深度优先遍历,图的深度优先遍历类似于树的先序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。 用此方
15、法遍历图就很自然地称之为图的深度优先遍历。,假设初始状态是图中所有顶点未曾被访问，首先从图中某个顶点发v出发，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。,1. 深度优先遍历的递归定义,2.基本实现思想：,（1）访问顶点v； （2）从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历； （3）重复上述两步，直至图中所有和v有路
16、径相通的顶点都被访问到。 如图6-19所示访问路线。,以图6-20的无向图为例，进行图的深度优先搜索。假设从顶点v1出发进行搜索，在访问了顶点v1之后，选择邻接点v2。因为v2未曾访问，则从v2出发进行搜索。依次类推，接着从v4 、v8 、v5 出发进行搜索。在访问了v5之后，由于v5的邻接点都已被访问，则搜索回到 v8。由于同样的理由，搜索继续回到v4，v2直至v1，此时由于v1的另一个邻接点未被访问，则搜索又从v1到v3，再继续进行下去由此，得到深度优先遍历的顶点访问序列为: v1 v2 v4v8 v5 v3v6v7,显然，这是一个递归的过程。为了在遍历过程中便于区分顶点是否已被访问，需附设访问标志数组visited0:n-1, ，其初值为FALSE ，一旦某个顶点被访问，则其相应的分量置为TRU
