《高等教育自学考试网上辅导《数据结构导论》5》由会员分享，可在线阅读，更多相关《高等教育自学考试网上辅导《数据结构导论》5（17页珍藏版）》请在金锄头文库上搜索。
1、 第 5 章 图 打印本页本章学习时，要弄清有关的基本概念，掌握图的两种存储方法，掌握图的两种遍历方法，不 但要会遍历，而且要清楚算法的步骤和语句，能根据算法遍历给定的图。弄清有关最小生成树和 拓扑排序的内容，要熟练地掌握求出给定带权图后求最小生成树的方法和给定有向图后求出拓扑 序列的方法。5.1 图的基本概念（1）图的定义图G是由有限非空结点集V与顶点偶对集E（也称边）组成的非线性结构，记为G=（V，E）。通常，也将图G的顶点集和边集分别记为V（G）和E（G）。E（G）可以是空集，此时图G有顶 点而无边。顶点集：构成图的顶点的集合，记为V（G），不能为空。边集：构成图的顶点偶对（即边）的集合
2、，记为E（G），它可以是空集。 例如，图G1，G2和G3分别可描述如下：图G1=（V1，E1）V1=v1，v2，v3E1=，它有三个顶点和三条有向边。 图G2=（V2，E2）V2=v1，v2，v3，v4E2=（v1，v2），（v1，v3），（v1，v4），（v2，v3），（v2，v4），（v3，v4）它有四个顶点和六条无向边。 图G3=（V3，E3）V3= v1，v2，v3，v4，v5，v6，v7E3=（v1，v2），（v1，v3），（v2，v4），（v2，v5），（v3，v6），（v3，v7）它有七个顶点和六条无向边。在下面的讨论中，不考虑顶点到自己的边，即若（x，y）或是E（G）中的一条边
3、，则 要求xy。此外，也不允许一条边在图中重复出现。这意味着，本课程研究的是简单的图。 （2）子图设构成图G的有限非空结点集V（G）的子集为V，顶点偶对集合E（G）的子集为E，且E 中边所关联的顶点均在V中，则由V和E构成的图称为图G的子图，记为G=（V，E）。下面，给出了图G1的若干个子图和图G2的若干个子图，它们的第一个子图的V都为 v1， 而E都为空，即E=。这些子图都符合上述子图的定义。在图G2的子图中，若定义V2= v1，v2，v3，则对于G2而言，后面的两个图就不能称为是它的子图了，应为，虽然E=（v2，v4），（v3，v4）和（v1，v4），（v2，v4），（v3，v4）都是E的
4、子集，但其中的v4?V2，与子图定义不符，故它们不是G2的子图，且也不是图。 （3）有向图若图G中的每条边都是有方向的，则称该图为有向图（Digraph）。有向图中，以表示从顶点x到顶点y的顶点偶对，即从顶点x到顶点y的有向边。因为边 是有向的，所以边和代表着两条不同的边。后者为从顶点y到顶点x的有向边。弧：设x，yV，若E，则表示有向图G中从顶点x到顶点y的一条弧，即有向 图G中的有向边称为弧。弧尾或始点：在有向图G中从顶点x到顶点y的弧中的顶点x，即有向边的起始点。弧头或终点：在有向图G中从顶点x到顶点y的弧中的顶点y，即有向边的终止点。图G1=（V1，E1）是一个有向图，它由顶点集V1=
5、v1，v2，v3和顶点偶对（边）集E1=，组成。边集中包括三条有向边或称为三条弧，和。边的弧尾或始点为顶点v1，弧头或终点为顶点v2。边的弧尾或始点为顶点v2，弧头或终点为顶点v1。若在无向图中，它们是同一条边。对于有向图，它们的顶点数n和边数e的关系是：0en*（n-1）。（4）无向图顶点偶对无序，即图的边无方向，这样的图称为无向图。无向图的边以（x，y）表示，因为 是无向的，所以边（x，y）和 （y，x） 表示同一条边。图G2和G3都是无向图。它们中的边都是无方向的。即（v1，v2）和（v2，v1）表示同一条 边。对于无向图，它们的顶点数n和边数e的关系是：0en*（n-1）/2。 （5）
6、点的相邻和边的关联互邻：在无向图G中，若顶点x和顶点y之间有条边（x，y），则称顶点x和顶点y互为邻接 点，即它们互邻。图G2中，与顶点v1相邻的顶点是v2、v3和v4，而关联到顶点v2的边是（v1，v2），（v2，v4） 和（v2，v3）。 相邻：在有向图G中，若顶点x和顶点y之间有条边，则称顶点x邻接到顶点y，或顶点y 邻接于顶点x。关联：在无向图G中，若顶点x与顶点y互邻，即存在边（x，y），则称顶点x和顶点y与边 （x，y） 相关联。在有向图G中，若顶点x和顶点y之间有条边，则称边关联到顶点 x和顶点y。图G1中，关联到顶点v2的边是、和。顶点v1邻接到顶点v2，顶点v2邻接到顶点v1
7、和v3；顶点v2邻接于顶点v1，顶点v1和v3邻接于顶点v2。 （6）完全图无向完全图：任何两点之间都有边相关联的无向图称为无向完全图。具有n个顶点的无向完 全图的边数为n*（n-1）/2。图G2是一个无向完全图，它有四个顶点和六条边。 有向完全图：任何两点之间都有弧的有向图称为有向完全图。具有n个顶点的有向完全图的 边数为n*（n-1）。（7）权与度权：图的边或弧所带的数值称为权。带权图或网：每条边或弧都带权的图称为带权图或网。度：无向图中，顶点v的度是与该顶点相关联的边的数量，记为D（v）。例如，图G2的各顶点的度为：顶点 v1 v2 v3 v4度 3 3 3 3入度：有向图中，以顶点v为
8、终点的弧的数量称为顶点v的入度，记为ID（v）。例如，图G1的各顶点的入度为：顶点 v1 v2 v3入度 1 1 1出度：有向图中，以顶点v为始点的弧的数量称为顶点v的出度，记为OD（v）。例如，图G1的各顶点的出度为：顶点 v1 v2 v3出度 1 2 0可见，有向图中，各顶点出度之和与入度之和是相等的。但无论是有向图还是无向图，顶点 数n、边数e和度之间有如下的关系：（8）路径与回路路径：无向图G=（V，E）中，从顶点v到顶点v的路径是一个顶点序列（v=vi0，vi1，vi2，vin=v），其中（vij-1，vij）E，1jn。若G是有向图，则路径是有向的。例如，图G2中v1，v2、v3、
9、v1、v4、v2就是一条路径，它是无向的；图G1中v1，v2、v1、v2、 v3就是一条有向路径。简单路径：组成路径的序列中，顶点不重复出现的路径称为简单路径。上述图G1和图G2的路径都不是简单路径，因为其中都有顶点重复出现。若改成图G2中的路径为v1，v2、v3、v4；图G1中的路径为v1，v2、v3，则它们都是简单路径了。路径长度：组成路径的边或弧的数量。环或回路：第一个顶点和最后一个顶点相同的路径称为环或回路。简单回路或简单环：除第一个顶点和最后一个顶点外，其余顶点都不重复的环或回路称为简 单回路或简单环。（9）连通连通：图中若从顶点v到顶点v有路径，则称顶点v和顶点v是连通的。连通图：
10、若对于图G中任意两个顶点v，vV，且v和v都是连通的，则称G为连通图。连通子图：由连通图中部分顶点组成的连通的部分称为连通子图。连通分量：无向图G中的极大连通子图。（10）生成树生成树：一个连通图的生成树是含有该连通图全部顶点的一个极小连通子图，即含有最少边 的连通子图。生成树的边数：若连通图G的顶点个数为n，则G的生成树的边数为n-1。由此可判断，若G的一个子图G的边数大于n-1，则G中一定有环。反之，若G的边数小 于n-1，则G一定不连通（G的顶点数与G的顶点数相同时）。5.2 图的存储5.2.1 图的顺序存储（1）一般图（无权）的顺序表示图的顺序存储实际上是使用一个n*n（n是图的顶点数
11、）的矩阵来存储图。邻接矩阵A的元素Aij的值满足如下条件： = 1，若（vi，vj）或vi,vj为图上的一条边； = 0，否则。可见，邻接矩阵的存储空间与图上的顶点数成正比。邻接矩阵的数据结构可以说明如下：#define vnum 20typedef struct graph VertexType vexsvnum; /* 顶点信息 */int arcsvnumvnum; /* 邻接矩阵 */int vexnum,arcnum; /* 顶点数，弧（边）数 */ GraphTp;若图的顶点除编号外，无其它信息，则只要定义一个数组即可，如：#define vnum 20typedef GraphT
12、pvnumvnum;（2）带权图（网络）的顺序表示带权图的顺序存储实际上也是使用一个n*n（n是图的顶点数）的矩阵来存储。表示带权图的邻接矩阵A的元素Aij的值满足如下条件：= wij，若（vi，vj）或vi,vj为带权图上的一条边，wij为边上的权值；=，否则。可见，带权图的邻接矩阵的存储空间也与图上的顶点数成正比。邻接矩阵的数据结构可以说明如下：#define INT_MAX 32767typedef struct graph VertexType vexsvnum; /* 顶点信息 */WeightType arcsvnumvnum; /* 邻接矩阵 */int vexnum,arcnu
13、m; /* 顶点数，弧（边）数 */ GraphTp;（3）图的邻接矩阵存储实例1）有向图如下所示，请给出它的邻接矩阵表示。由于共有四个结点，所以邻接矩阵为一个4*4的二维数组，如下所示： 0 1 1 0 由于结点到结点、各有一条有向边。 0 0 0 1 由于结点到结点有一条有向边。 0 0 0 1 由于结点到结点有一条有向边。 1 0 0 0 由于结点到结点有一条有向边。2）有网络如下图所示，请给出它的邻接矩阵表示。由于共有五个结点，所以邻接矩阵为一个5*5的二维数组，如下所示：结点v1到结点v2、v3和v4各有一条边，权值各为3，5，8。结点v2到结点v1、v3、v4和v5各有一条边，权值
14、各为3，6，4,11。结点v3到结点v1、v2和v4各有一条边，权值各为5，6，2。结点v4到结点v1、v2，v3，v5各有一条边，权值为8，4，2，10。结点v5到结点v2和v4各有一条边，权值各为11，10。（4）图的邻接矩阵存储时各顶点的度利用邻接矩阵很容易判定任意两个顶点之间是否有边（或弧）相关联，并容易求得各顶点的度。1）无向图的度顶点vi的度D（vi）是邻接矩阵中第i行（或第i列）的元素之和，即：2）有向图的度顶点vi出度OD（vi）的是邻接矩阵中第i行的元素之和，即：顶点vi的入度ID（vi）是邻接矩阵中第i列的元素之和，即28：32处老师口误，应是“ID（vi）”，而不是“DI
15、（vi）”。5.2.2 图的链式存储（1）图的邻接表存储图的邻接表存储实际上是以一种链表形式来存储图。在这种表示方式中，对每个顶点都建立 了一个单链表，若该顶点到另一个顶点有一条边，则在此单链表中有一个结点。每个单链表的头 结点组成了一个指针数组，它的指针指向所属单链表的第一个结点。因此，为了存储图，用到了 两种链表结点。用C语言语句表示如下：#define vnum 20 /* 最大顶点数 */typedef struct arcnode /* 邻接表中边结点的数据结构 */ int adjvex; /* 下一条弧（边）的弧头（始点）编号 */*WeightType wt; 若用邻接表表示带
16、权图的话，用这个变量存储权值 */struct arcnode *nextarc; / 指向下一条弧（边）的指针 */ ArcNodeTp;typedef struct vexnode /* 邻接表头结点的数据结构 */ int vertex; /* 顶点编号 */ArcNodeTp *firstarc; /* 指向第一条边的指针 */ AdjListvnum;typedef struct graph /* 图的邻接表结构 */ AdjList adjlist;int vexnum,arcnum; /* 图中顶点和边的个数 */ GraphTp;（2）图的邻接表存储实例1）有向图如下所示，请给出它的邻接矩阵和邻接表表示。该有向图的邻接表如下所示：2）有网络如下图所示，请给出它的邻接矩
