《《算法与数据结构》第5章 图与网151》由会员分享，可在线阅读，更多相关《《算法与数据结构》第5章 图与网151（151页珍藏版）》请在金锄头文库上搜索。
1、算法与数据结构,第5章 图与网,第5章 图与网,图与网是更为复杂的数据结构，数据元素之间的关系既不是线性表中的一对一的邻接关系，也不是树型结构中的一对多的层次关系，而是一种多对多的网状关系，任意两个数据元素之间都可能相关。 由于许多问题都可以用图或网来表示，所以其应用已渗透到语言学、逻辑学、物理、化学、电子、通讯、数学等诸多学科领域。,第5章 图与网,5.1 图与网的基本概念 5.2 图与网的存储结构 5.3 图的遍历 5.4 无向连通网的最小生成树 5.5 有向网的最短路径 5.6 有向无环图及其应用,5.1 图与网的基本概念,5.1.1 图与网的定义 5.1.2 图的相关术语,图的定义,图
2、（graph）是由非空的顶点集合V和描述顶点间关系的弧（或边）的集合E组成的二元组，即G=(V，E) 其中： V=vi | vidataobject，E= | vi , vjV， dataobject是具有相同性质的数据元素（即顶点）的集合； 表示从vi到vj有一条边单向相连称作弧，且称vi为弧尾（起点），vj为弧头（终点），此时称图为有向图（digraph）。 若E，必有E，则可以用无序对（vi , vj）代替这两个有序对，即从vi 到 vj有一条双向边（即无向边，也可看作双向边）相连称作边，此时图称为无向图（undigraph）。,图的示例,G1=(V1，E1) 其中： V1=v1，v2，
3、v3，v4， E1=，；,G2=(V2，E2) 其中： V2=v1，v2，v3，v4，v5， E2=(v1，v2)，(v1，v4)，(v2，v3)，(v2，v5)，(v3，v4)，(v3，v5),图的定义（续）,如果用n表示图中顶点数目，用e表示边或弧的数目，且不考虑顶点到自身的边或弧，那么对于无向图e的取值范围是0到n(n-1)/2，而对于有向图e的取值范围为0到n(n-1)。 把具有n(n-1)/2条边的无向图称为无向完全图； 把具有n(n-1)条弧的有向图称为有向完全图； 有向完全图和无向完全图统称完全图（completed graph）。 若图中边或弧的数目很少则称为稀疏图（spars
4、e graph），反之边或弧的数目接近完全图则称为稠密图（dense graph）。,子图的定义,假设有两个图G=（V，E）和G=（V，E），如果V V且E E，则称G是G的子图（subgraph）。 子图示例如下：,网的定义,把图中与边或弧相关的数称之为权(weight)；权可以表示从一个顶点到另一个顶点的距离、时间、电流、电压、耗费等， 通常把这种带权图称作网（network）； 当然也可以依据边或弧有无向网和有向网的概念。 网的示例如下图：,5.1 图与网的基本概念,5.1.1 图与网的定义 5.1.2 图的相关术语,图的相关术语,在无向图中，某个顶点的度（degree）是指所依附于该顶
5、点的边的数目，顶点v的度通常记作TD（V）。例如在无向图G2中，TD（v1）=2，TD（v2）=3，TD（v3）=3，TD（v4）=2，TD（v5）=2。,在有向图中要区别顶点的入度和出度的概念， 入度是指以顶点V为终点的弧的数目，通常记作ID(V)； 出度是指以顶点V为始点的弧的数目，通常记作OD(V)； 顶点的度定义为入度和出度的和，即:TD（V）=ID（V）+OD（V）。,图的相关术语（续）,例如在有向图G1中， ID（v1）=1，OD（v1）=2，TD（v1）=3； ID（v2）=1，OD（v2）=0，TD（v2）=1； ID（v3）=1，OD（v3）=1，TD（v3）=2； ID（v
6、4）=1，OD（v4）=1，TD（v4）=2。,一般地，对于具有n 个顶点e条边或弧的图，边或弧的个数与各顶点的度TD（vi）之间满足如下关系：,图的相关术语（续）,在无向图G=（V，E）中，若（vp，vi1），（vi1，vi2） （vin，vq）都是E中的边，则称结点序列vp，vi1，vi2 vin，vq为从vp到vq的一条路径； 在有向图中，则要求， 都是E中的弧。 路径（path）长度定义为路径上边或弧的数目； 如有向图G1中有，所以说从V3到V2存在一条长度为3的路径； 如无向图G2有(v1，v2)，(v2，v5)和(v1，v4)，(v4，v3)，(v3，v5)，所以说从V1到V5存在
7、一条长度各为2和3的路径。,图的相关术语（续）,如果顶点序列中不出现重复顶点，则称顶点序列为简单路径，例如前面所举三条路径的顶点序列分别为v3、v4、v1、v2和v1、v2、v5与v1、v4、v3、v5，均无重复顶点出现都是简单路径。 第一个顶点和最后一个顶点相同（即vp =vq）的简单路径称为简单回路或环（cycle）， 例如在有向图G1中的v1，v3，v4，v1和无向图G2中的v1，v4，v3，v2，v1与v2，v3，v5，v2等都是简单回路或环。,图的相关术语（续）,在无向图中，如果从一个顶点vi到另一个顶点vj 有路径，则称vi和vj是连通的；如果图中任意两个顶点vi和vj都是连通的，
8、则称该无向图是连通图（connected graph）。例如无向图G2是连通图，,而如下无向图G5是非连通图。,图的相关术语（续）,无向图的极大连通子图称为图的连通分量（connected component）。 例如下图给出了无向图G5的两个连通分量。,图的相关术语（续）,在有向图中，如果对于任意两个顶点vi和vj（vivj）从vi到vj和从vj到vi都存在路径，则称该有向图为强连通图（strong graph）。 有向图的极大强连通子图称为图的强连通分量（strongly connected component）。 例如有向图G1不是强连通图，它的两个强连通分量如下图所示。,图的相关术语（
9、续）,一个连通图的生成树（spanning tree）是该图的一个极小连通子图，它包含图中全部的n个顶点和连通这n个顶点的n-1条边。 如果在生成树上添加任意一条原图中的其它边必定会产生回路或环；换句话说，有n个顶点n条或n条以上边的无向图一定存在回路或环。如果n个顶点的图其边数少于n-1条，则一定是非连通图。 例如无向图G2的一棵生成树如下图所示。,图的相关术语（续）,在非连通图中，由每个连通分量都可以得到一个极小连通子图，即一棵生成树，这些连通分量的生成树就构成了该非连通图的生成森林。 对于有向图，其生成树或生成森林必定是有向树和有向森林。 例如无向图G5的生成森林如下图所示。,第5章 图
10、与网,5.1 图与网的基本概念 5.2 图与网的存储结构 5.3 图的遍历 5.4 无向连通网的最小生成树 5.5 有向网的最短路径 5.6 有向无环图及其应用,图和网的存储结构,由于图的结构复杂，其数据元素间存在着多对多的网状关系，所以无法用物理位置关系表示元素间的逻辑关系，即不存在顺序存储结构； 但可借用数组来表示元素间的逻辑关系。由于图中顶点的度差别一般较大，故也不宜采用多重链表存储结构； 但可根据图的具体情况和需要进行的操作，设计恰当的结点结构和表结构来存储顶点信息和顶点间的关系，,5.2 图与网的存储结构,5.2.1 邻接矩阵 5.2.2 邻接表与逆邻接表 5.2.3 邻接多重表,邻
11、接矩阵,所谓邻接矩阵（adjacency matrix）存储结构，就是用一维数组存储图或网的顶点信息，用二维数组表示顶点之间的邻接关系（即邻接矩阵）。 若G=（V，E）是具有n个顶点的图或网，G的邻接矩阵A是如下定义的n阶方阵： 当G是无向图或有向图时，矩阵A中元素定义为,邻接矩阵（续）,当G是无向网或有向网时，矩阵A中元素定义为 其中：Wij表示边或弧上的权值，表示一个所用计算机上所允许的大于所有权值的数或者一个特殊的其它值。,邻接矩阵存储结构举例,邻接矩阵存储,邻接矩阵存储,邻接矩阵存储结构举例(续),邻接矩阵存储,邻接矩阵存储,邻接矩阵存储结构的特点,从图的邻接矩阵存储表示容易看出该表示
12、法具有如下特点： 无向图或网的邻接矩阵一定是一个对称矩阵，因此在存储邻接矩阵时可以只存储其上三角阵或下三角阵以节省存储空间。 对于无向图或网，其邻接矩阵中第i行（或第i列）中非零元素（或非元素）的个数正好是第i个顶点的度。即,邻接矩阵存储结构的特点(续),对于有向图或网，其邻接矩阵中第i行中非零元素（或非元素）的个数正好是第i个顶点的出度OD(vi)，而第i列中非零元素（或非元素）的个数正好是第i个顶点的入度ID(vi) 。即 很容易确定图或网中任意两个顶点之间是否有边或弧相连；但要确定图或网中有多少条边或弧则需要逐行逐列扫描方阵，时间代价是O(n2)，这是该方法的局限性。,邻接矩阵存储图或网
13、的类型定义,用一维数组存储顶点信息，用邻接矩阵存储顶点间关系信息的图或网的形式描述如下：#define maxvernum 100#define infinity maxintegertypedef structvertextype vexmaxvernum;int adjmatrixmaxvernummaxvernum; int n,e; /*定义顶点数和边或弧数变量单元*/mgraph;,5.2 图与网的存储结构,5.2.1 邻接矩阵 5.2.2 邻接表与逆邻接表 5.2.3 邻接多重表,邻接表,邻接表（adjacency list）是图和网的一种链式存储结构。在邻接表中，对图或网中的每个
14、顶点建立一个单链表，第i个单链表中的结点是与vi相关联的边所联结的结点（对有向图是以顶点vi为尾的弧所联结的结点，即弧头结点）。 每个结点由三个域组成，其中：邻接点域adjvex指示与顶点vi邻接的点在图中的位置，链域next指示下一条边或弧所联结的结点，数据域info存储和边或弧相关的信息（如网中的权值等）。每个单链表都附设一个表头结点，如下图所示。,邻接表（续）,除了设有链域next指向链表中的第一个结点外，还设有数据域data存放顶点vi的有关信息（如顶点名，顶点位置等）。 这些表头结点也可以组织为一个链表，但通常以向量形式存储于一维数组中，以方便随机访问任一顶点的单链表。 例如有向网G
15、3的邻接表如下图所示。,邻接表举例,无向网G4的邻接表如下图所示。,邻接表中结点和表头结点的形式描述,邻接表中结点和表头结点的形式描述定义如下：#define maxvernum 100typedef struct node /*定义表结点结构*/int adjvex,info;struct node *next; nodetype;typedef struct frontnode /*定义表头结点结构*/vertextype data; struct node *next; frontnodetype;typedef frontnodetype adjlistmaxvernum;,邻接表与逆
16、邻接表,若无向图或网中有n个顶点e条边，则它的邻接表需n个表头结点和2e个表结点。显然在边稀疏的情况下，用邻接表比邻接矩阵节省存储空间，当与边相关的信息较多时更是如此。 在无向图或网的邻接表中，顶点vi的度恰为第i个链表中的结点数。在有向图或网的邻接表中，第i个链表中的结点数只是顶点vi的出度；为了求vi的入度，必须遍历整个邻接表，所有邻接点域adjvex的值为i的结点个数是顶点vi的入度。 有时为了便于确定顶点的入度或以vi为头的弧，可以建立逆邻接表，即对vi建立一个链接以vi为头的弧的表。 在邻接表上，可以很方便地找到任一顶点的第一个邻接点和下一个邻接点；但要判定任意两个顶点vi和vj之间是否有边或弧相连，则需要第i个或第j个单链表，在这一点上不及邻接矩阵方便。,逆邻接表举例,有向网G3的逆邻接表如下图所示,5.2 图与网的存储结构,
