武汉软件工程职业学院《数据结构讲义》第16讲 图new

1、第十六讲 图第五章 图1掌握图的定义及基本术语。2. 掌握图的存储结构（包括邻接矩阵和邻接表），以及这些存储表示上的典型操作。 教学重点：1、 图的定义及其基本概念（包括图的定义，图的连通性，图的路径和路径长度，图中各顶点的度，有向图和无向图的概念，完全图，子图的概念。无向连通图的强连通分量，有向强连通图的强连通分量等2、图的存储结构。 教学难点： 图的存储结构 授课内容第5章 图图(Graph)是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层

2、中多个元素(即其孩子结点)相关，但只能和上一层中一个元素(即其双亲结点)相关；而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。由此，图的应用极为广泛，特别是近年来的迅速发展，已渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。5.1 图的基本概念在图中的数据元素通常称做顶点(Vertex)，V是顶点的有穷非空集合；E是用顶点对表示的边（Edge）的有穷集合。若VR必有VR，即E是对称的，则以无序对(vi,vj)代替这两个有序对，表示vi和vj之间的一条边（Edge)，此时的图称为无向图(Undigraph)。若E，则表示从vi 到v

3、j的一条弧(Arc)，且称v为弧尾(Tail)或初始点(Initial node)，称vj为弧头(Head)或终端点(Terminal node)，此时的图称为有向图(Digraph)。 例如 图5-1-1给出两个图G1和G2，其中G1是无向图，G2是有向图。在有向图中用箭头表示弧的方向，箭头从弧尾指向弧头。 图G1 图G2图5-1-1 有向图与无向图在上面两个图结构中，一个是有向图，即每条边都有方向，另一个是无向图，即每条边都没有方向。例如 图5-1-2(a)中G3是有向图，定义此图的谓词P(vi，vj )则表示从vi到vj的一条单向通路。G1=(V1,A1)其中：V1=v1,v2,v3,v

4、4A1=,图5-1-2 (b)中G4为无向图G2=(V2,A2)其中：V2=v1,v2,v3,v4,v5A2=(v1,v2),(v1,v4),(v2,v3) ,(v2,v5),(v3,v4),(v3,v5)（a)有向图G3 (b)无向图G2图5-1-2图的示例5.1.2 图的基本术语 在下面的讨论中，不考虑顶点到其自身的边或弧在图中重复出现，同时可以用n表示图中顶点的数目，用e表示边或弧的数目。 邻接点、相关边对于无向图G=（V，E），若边（vi，vj）E，则称vi和vj互为邻接点（Adjacent），即vi和vj相邻接，而边（vi， vj ）则是与顶点vi和vj相关联的边。对于有向图G=（V

5、，A），若弧（vi，vj）E，则称为顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，而弧（vi， vj ）和顶点vi、 vj相关联。 完全图：在一个有n个顶点的无向图中，若每个顶点到其它（n-1）个顶点都连有一条边，则图中共有n(n-1)/2条边，这种图称为完全图（Complete graph，也称完备图）。 左图所示就是n=4的完全图，它一共有六条边。 子图：设有两个图G =(V,E)和G=(V,E)，若V(G)是V(G)的子集，且E(G)是E(G)的子集，则称G是G的子图(Subgraph)。例如 图5-1-3所示的图是图5-1-1中G1的一些子图。 图5-1-3 子图 例如 图5-1-4

6、是子图的一些例子。 图5-1-4 顶点的度：图中与每个顶点相连的边数，叫该顶点的度(Degree)。例如图5-1-2的图G1中，顶点的度数为2，顶点的度数为3，。对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。例如在图5-1-1的图G2中，顶点的入度为1，出度为2，而顶点的入度为1，出度为0，因为有一条边指向它，而没有边从它指出去。可以证明，一个有n个顶点，e调边或弧的图，满足如下关系： 路径：在一个图中，若从某顶点Vp出发，沿一些边经过顶点V1,V2,Vm到达Vq， 则称顶点序列(Vp, V1,V2,Vm,

7、Vq)为从Vp到Vq的路径(Path)。路径长度：对于无权的图，路径长度指的是沿此路径上边的数目；对于有权图，一般是取沿路径各边的权之和作为此路径的长度。若一条路径上各顶点均不重复，即路径经过每一顶点不超过一次，则此路径叫做简单路径。如果从一个顶点出发又回到该顶点，即Vp与Vq相同，则此路径叫做回路或环（Cycle）。 连通、连通图：在无向图中，如果从顶点Vi到顶点Vj之间有路径，则称这两个顶点是连通的。如果图中任意一对顶点都是连通的，则称此图是连通图(Connected graph)。例如图5-1-1中的图G1是连通图。图5-1-5（a）中的图G3就是非连通图，非连通图的每一个极大连通子图叫

8、连通分量(Connected Component)，此图包括二个连通分量，见图5-1-5（b）。 V0V1V2V3V4V2V3V4V5V0V1V4V5 （a） 图G3 （b）图G3的连通分量 图5-1-5 图的连通分量例如图5-1-6 (a)中的G4也是是非连通图，G4有三个连通分量，如图5-1-6 (b)所示。 （a）无向图G4 （b）G4的三个连通分量图5-1-6无向图及其连通分量在有向图G中，如果对于每一对vi,vj V ，vi!=vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。例如图5-1-4 (a)中的G1，不是强连通图，

9、但它有两个强连通分量，如图5-1-7所示。 图5-1-4（a）有向图G1 图5-1-7 G1的两个强连通分量l 权和网络：有些图， 对应每条边有一相应的数值，这个数值叫做该边的权(Weight)。边上带权的图称为带权图，也称为网络(Network)。图5-1-8所示就是一个网。V0V1V2V36476 图5-1-8 网的示例5.2 图的存储结构5.2.1 邻接矩阵表示法邻接矩阵是表示顶点之间相邻关系的矩阵。所谓两顶点的相邻关系即它们之间有边相连。邻接矩阵是一个（nn）阶方阵，n为图的顶点数，它的每一行分别对应图的各个顶点，它的每一列也分别对应图的各个顶点。定义一个有n阶的方阵A（邻接矩阵）存储

10、点的关系： 例如，图 5-1-4中G1和G2的邻接矩阵如图5-1-9所示。以二维数组表示有n个顶点的图时，需存放n个顶点信息和n2个弧信息的存储量。若考虑无向图邻接矩阵的对称性，则可采用压缩存储方式只存入矩阵的下三角(或上三角)元素。图5-1-9图的邻接矩阵借助于邻接矩阵容易判定任意两个顶点之间是否有边(或弧)相连，并容易求得各个顶点的度。对于无向图，顶点i的度是邻接矩阵中第i行(或第i列)的元素之和，即 n-1 TD( vi )=Aij (n=MAX_VERTEX_NUM) j=0对于有向图，第i行的元素之和为顶点vi的出度OD(vi)，第j列的元素之和为顶点vj的入度ID(vj)。网的邻接

11、矩阵可定义为 例如，图5-1-10列出了一个网有向和它的邻接矩阵。 图5-1-10 网及其邻接矩阵 图的邻接矩阵具有以下特点： 无向图的邻接矩阵是对称的 如果Ai，j=1，必有Aj，i=1。这说明，只输入和储其上三角阵元素即可得到整个邻接矩阵。 一般有向图的邻接矩阵是不对称的，Ai，j不一定等于Aj，i。 邻接矩阵用二维数组即可存储，定义如下： int adjmatrix = ARRAYnn; 如果图的各边是带权的，只需将矩阵中的各个1元素换成相应边的权即可。下面给出图的邻接矩阵表示的存储形式说明以及无向图的建立算法。#define VEX-NUM 10 /*顶点数目*/typedef cha

12、r Vextype; /*顶点类型*/typedef structVextype vexsVEX_NUM; /*顶点向量*/Int arcsVEX_NUMVEX_NUM; /*邻接矩阵*/ Magraph;算法5.1 void creat_Mgraph (Mgraph *G,int e) for(i=0;ivexsi); for(i=0;iVEX_NUM;+i) for(j=0;jarcsij=0; for(k=0;karcsij=1;G-arcsij=1; /*creat_Mgraph*/ 从算法5.1可以看出其指向时间是O（n+n2+e），其中O（n2）的时间耗费在邻接矩阵的初始化操作上。

13、因为en，所以，算法5.1的时间复杂度是O（n2）。5.2.2 邻接表图的邻接表(AdjacencyList)是一种顺序分配和链式分配相结合的存储结构。在邻接表结构中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于该顶点Vi的边，即对于无向图每个结点表示与该顶点相邻接的一个顶点；对于有向图则表示以该顶点为起点的一条边的终点。一个图的邻接矩阵表示是唯一的，但其邻接表表示是不唯一的。因为在邻接表的每个单链表中，各结点的顺序是任意的。邻接表中每个表结点均由两个域组成，如图5-2-2（a）所示，其一是邻接点域（adjvex），用以存放与顶点Vi相邻接的顶点在图中的位置；其二是链域（nex

14、t），用以指向依附于顶点Vi的下一条边所对应的结点。如果用邻接表存放网络中的信息，则还需要在结点中增加一个存放权值的域,称为数据域（weighth）。在每个链表设一表头结点，一般这些表头结点本身以向量的形式存储。如图5-2-2（b）所示。 adjvexnextarcweighthdata firstarc （a）表结点 （b） 头结点 图5-2-2 结点结构 所以表头结点以顺序存储结构的形式存储，即以一维数组表示，数组的下标指示了顶点的序号，这样就可以随机访问一个顶点的链表。图的邻接表存储结构描述如下：#define VEX_NUM 10typedef char Vextype;typedef

15、 struct arcnode int adjvex; struct arcnode *next; ArcNode;typedef struct vnode Vextype data; arcnode *firstarc;VNode; typedef VNode AlgraphVEX_NUM; 例如，图5-2-3 (a)和(b)所示分别为图5-1-4中Gl和G2的邻接表。 图5-2-3对于无向图的邻接表来说，一条边对应两个单链表结点，邻接表结点总数是边数的2倍。在无向图的邻接表中，各顶点对应的单链表的结点数（不算表头结点）就等于该顶点的度数。在有向图邻接表中，一条弧对应一个表结点，表结点的数目和弧的数目相同。在有向图邻接表中，单链表的结点数就等于相应顶点的出度数。要求有向图中某顶点的入度数，需扫视邻