第7章 图,图(Graph)是一种比线性表和树更为复杂的数据结构。线性结构：是研究数据元素之间的一对一关系。在这种结构中，除第一个和最后一个元素外，任何一个元素都有唯一的一个直接前驱和直接后继。树结构：是研究数据元素之间的一对多的关系。在这种结构中，每个元素对下(层)可以有0个或多个元素相联系，对上(层)只有唯一的一个元素相关，数据元素之间有明显的层次关系。,图结构：是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相关。图的应用极为广泛，已渗入到诸如语言学、逻辑学、物理、化学、电讯、计算机科学以及数学的其它分支。,7.1 图的基本概念,7.1.1 图的定义和术语一个图(G)定义为一个偶对(V,E) ，记为G=(V,E) 。其中： V是顶点(Vertex)的非空有限集合，记为V(G)；E是无序集V&V的一个子集，记为E(G) ，其元素是图的弧(Arc)。将顶点集合为空的图称为空图。其形式化定义为： G=(V ，E) V=v|vdata object E=| v,wVp(v,w) P(v,w)表示从顶点v到顶点w有一条直接通路。,弧(Arc) ：表示两个顶点v和w之间存在一个关系，用顶点偶对表示。通常根据图的顶点偶对将图分为有向图和无向图。有向图(Digraph)： 若图G的关系集合E(G)中，顶点偶对的v和w之间是有序的，称图G是有向图。在有向图中，若 E(G) ，表示从顶点v到顶点w有一条弧。 其中：v称为弧尾(tail)或初始点(initial node)，w称为弧头(head)或终端点(terminal node) 。无向图(Undigraph)： 若图G的关系集合E(G)中，顶点偶对的v和w之间是无序的，称图G是无向图。,在无向图中，若E(G) ，有E(G) ，即E(G)是对称，则用无序对(v,w) 表示v和w之间的一条边(Edge)，因此(v,w) 和(w,v)代表的是同一条边。 例1：设有有向图G1和无向图G2，形式化定义分别是： G1=(V1 ，E1) V1=a,b,c,d,e E1=, , , G2=(V2 ，E2) V2=a,b,c,d E2=(a,b), (a,c), (a,d), (b,d), (b,c), (c,d) 它们所对应的图如图7-1所示。,完全图：对于无向图，若图中顶点数为n ，用e表示边的数目，则e 0，n(n-1)/2 。具有n(n-1)/2条边的无向图称为完全无向图。 完全无向图另外的定义是：对于无向图G=(V，E)，若vi，vj V ，当vivj时，有(vi ,vj)E，即图中任意两个不同的顶点间都有一条无向边，这样的无向图称为完全图。,有向完全图：对于有向图，若图中顶点数为n ，用e表示弧的数目，则e0，n(n-1) 。具有n(n-1)条边的有向图称为有向完全图。 完全有向图另外的定义是：对于有向图G=(V，E)，若vi，vjV ，当vi vj时，有EE ，即图中任意两个不同的顶点间都有一条弧，这样的有向图称为有向完全图。有很少边或弧的图（enn）的图称为稀疏图，反之称为稠密图。 权(Weight)：与图的边和弧相关的数。权可以表示从一个顶点到另一个顶点的距离或耗费。,子图和生成子图：设有图G=(V，E)和G=(V，E)，若VV且EE ，则称图G是G的子图；若V=V且EE，则称图G是G的一个生成子图。顶点的邻接(Adjacent)：对于无向图G=(V，E)，若边(v,v)E，则称顶点v和v 互为邻接点，即v和w相邻接。边(v,v)依附(incident)与顶点v和v 。对于有向图G=(V ，E)，若有向弧E，则称顶点v “邻接到”顶点w，顶点w “邻接自”顶点v ，弧 与顶点v和w “相关联” 。顶点的度、入度、出度：对于无向图G=(V，E)， viV，图G中依附于vi的边的数目称为顶点vi的度(degree)，记为TD(vi)。,显然，在无向图中，所有顶点度的和是图中边的2倍。 即 TD(vi)=2e i=1, 2, , n ，e为图的边数。对有向图G=(V，E)，若vi V ，图G中以vi作为起点的有向边(弧)的数目称为顶点vi的出度(Outdegree)，记为OD(vi) ；以vi作为终点的有向边(弧)的数目称为顶点vi的入度(Indegree)，记为ID(vi) 。顶点vi的出度与入度之和称为vi的度，记为TD(vi) 。即 TD(vi)=OD(vi)+ID(vi) 路径(Path)、路径长度、回路(Cycle) ：对无向图G=(V，E)，若从顶点vi经过若干条边能到达vj，称顶点vi和vj是连通的，又称顶点vi到vj有路径。对有向图G=(V，E)，从顶点vi到vj有有向路径，指的是从顶点vi经过若干条有向边(弧)能到达vj。,或路径是图G中连接两顶点之间所经过的顶点序列。即 Path=vi0vi1vim ，vijV且(vij-1, vij)E j=1,2, ,m 或 Path=vi0vi1 vim ，vijV且E j=1,2, ,m路径上边或有向边(弧)的数目称为该路径的长度。在一条路径中，若没有重复相同的顶点，该路径称为简单路径；第一个顶点和最后一个顶点相同的路径称为回路(环)；在一个回路中，若除第一个与最后一个顶点外，其余顶点不重复出现的回路称为简单回路(简单环)。,连通图、图的连通分量：对无向图G=(V，E)，若vi ，vj V，vi和vj都是连通的，则称图G是连通图，否则称为非连通图。若G是非连通图，则极大的连通子图称为G的连通分量。 对有向图G=(V，E)，若vi ，vj V，都有以vi为起点， vj 为终点以及以vj为起点，vi为终点的有向路径，称图G是强连通图，否则称为非强连通图。若G是非强连通图，则极大的强连通子图称为G的强连通分量。 “极大”的含义：指的是对子图再增加图G中的其它顶点，子图就不再连通。,生成树、生成森林：一个连通图(无向图)的生成树是一个极小连通子图，它含有图中全部n个顶点和只有足以构成一棵树的n-1条边，称为图的生成树，如图7-2所示。关于无向图的生成树的几个结论： 一棵有n个顶点的生成树有且仅有n-1条边； 如果一个图有n个顶点和小于n-1条边，则是非连通图；, 如果多于n-1条边，则一定有环； 有n-1条边的图不一定是生成树。,有向图的生成森林是这样一个子图，由若干棵有向树组成，含有图中全部顶点。 有向树是只有一个顶点的入度为0 ，其余顶点的入度均为1的有向图，如图7-3所示。网：每个边(或弧)都附加一个权值的图，称为带权图。带权的连通图(包括弱连通的有向图)称为网或网络。网络是工程上常用的一个概念，用来表示一个工程或某种流程，如图7-4所示。,7.1.2 图的抽象数据类型定义,图是一种数据结构，加上一组基本操作就构成了图的抽象数据类型。 图的抽象数据类型定义如下： ADT Graph 数据对象V：具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R=VR VR=| v,wVp(v,w) ，表示 从v到w的弧，P(v,w)定义了弧的信息 ,基本操作P： Create_Graph() ： 图的创建操作。 初始条件：无。操作结果：生成一个没有顶点的空图G。GetVex(G, v) ： 求图中的顶点v的值。 初始条件：图G存在，v是图中的一个顶点。 操作结果：生成一个没有顶点的空图G。 DFStraver(G,V)：从v出发对图G深度优先遍历。初始条件：图G存在。操作结果：对图G深度优先遍历，每个顶点访问且只访问一次。, BFStraver(G,V)：从v出发对图G广度优先遍历。初始条件：图G存在。操作结果：对图G广度优先遍历，每个顶点访问且只访问一次。 ADT Graph 详见p156157。,7.2 图的存储结构,图的存储结构比较复杂，其复杂性主要表现在： 任意顶点之间可能存在联系，无法以数据元素在存储区中的物理位置来表示元素之间的关系。 图中顶点的度不一样，有的可能相差很大，若按度数最大的顶点设计结构，则会浪费很多存储单元，反之按每个顶点自己的度设计不同的结构，又会影响操作。图的常用的存储结构有：邻接矩阵、邻接链表、十字链表、邻接多重表。,7.2.1 邻接矩阵(数组)表示法,基本思想：对于有n个顶点的图，用一维数组vexsn存储顶点信息，用二维数组Ann存储顶点之间关系的信息。该二维数组称为邻接矩阵。在邻接矩阵中，以顶点在vexs数组中的下标代表顶点，邻接矩阵中的元素Aij存放的是顶点i到顶点j之间关系的信息。,1 无向图的数组表示 (1) 无权图的邻接矩阵无向无权图G=(V，E)有n(n1)个顶点，其邻接矩阵是n阶对称方阵，如图7-5所示。其元素的定义如下：,(2) 带权图的邻接矩阵无向带权图G=(V，E) 的邻接矩阵如图7-6所示。其元素的定义如下：,(3) 无向图邻接矩阵的特性 邻接矩阵是对称方阵； 对于顶点vi，其度数是第i行的非0元素的个数； 无向图的边数是上(或下)三角形矩阵中非0元素个数。 2 有向图的数组表示 (1) 无权图的邻接矩阵若有向无权图G=(V，E)有n(n1)个顶点，则其邻接矩阵是n阶对称方阵，如图7-7所示。元素定义如下：,(2) 带权图的邻接矩阵有向带权图G=(V，E)的邻接矩阵如图7-8所示。其元素的定义如下：, 有向图邻接矩阵的特性 对于顶点vi，第i行的非0元素的个数是其出度OD(vi)；第i列的非0元素的个数是其入度ID(vi) 。 邻接矩阵中非0元素的个数就是图的弧的数目。,3 图的邻接矩阵的操作图的邻接矩阵的实现比较容易，定义两个数组分别存储顶点信息(数据元素)和边或弧的信息(数据元素之间的关系) 。其存储结构形式定义如下： #define INFINITY MAX_VAL /* 最大值 */* 根据图的权值类型，分别定义为最大整数或实数 */ #define MAX_VEX 30 /* 最大顶点数目 */ typedef enum DG, AG, WDG,WAG GraphKind ;/* 有向图，无向图，带权有向图，带权无向图 */,#define VEX_NUM 20 typedef char Vextype； typedef struct Vextype vexsVEX_NUM; int adjVEX_NUMVEX_NUM; /*邻接矩阵*/ int n,e; /*顶点数和边数*/ Mgragh;,void CreateMGraph(Mgragh *G) int i,j,k,w; char ch;printf(“请输入顶点数和边数:n“);scanf(“%d,%d“, /*对称加入,无向图的邻接矩阵存储建立*/ /*CreateMGraph*/,7.2.2 邻接链表法,基本思想：对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。第i个单链表表示依附于顶点Vi的边(对有向图是以顶点Vi为头或尾的弧)。,1 结点结构与邻接链表示例链表中的结点称为表结点，每个结点由三个域组成，如图7-9(a)所示。其中邻接点域(adjvex)指示与顶点Vi邻接的顶点在图中的位置(顶点编号)，链域(nextarc)指向下一个与顶点Vi邻接的表结点，数据域(info)存储和边或弧相关的信息，如权值等。对于无权图，如果没有与边相关的其他信息，可省略此域。每个链表设一个表头结点(称为顶点结点)，由两个域组成，如图7-9(b)所示。链域(firstarc)指向链表中的第一个结点，数据域(data) 存储顶点名或其他信息。,