《《数据结构——用C语言描述（第二版）》-宁正元-电子教案 第7章 图》由会员分享，可在线阅读，更多相关《《数据结构——用C语言描述（第二版）》-宁正元-电子教案 第7章 图（77页珍藏版）》请在金锄头文库上搜索。
1、7.1 图的基本概念 7.2 图的存储结构 7.3 图的遍历 7.4 最小生成树 7.5 最短路径 7.6 AOV网与拓扑排序,第7章 图,图是比树形结构更为复杂的非线性结构。在线性结构中，除了开始结点和终端结点外，每个结点只有唯一的直接前趋和直接后继，结点之间存在一对一的线性关系；在树形结构中，结点之间存在一对多的层次关系，除根结点外，每个结点只能有一个直接前趋（即双亲），但每个结点允许有零或多个直接后继（即孩子），即每一层上的结点可以与它下面一层中的多个结点相关，但是只能和它上面一层的一个结点（双亲结点）相关。而在图结构中，数据元素之间的关系是一种多对多的网状关系，任意两个数据元素之间都可
2、能相关。 图的应用已渗透到语言学、逻辑学、物理、化学、电子、通讯、数学、计算机科学等诸多学科领域。 本章首先介绍图的概念，然后重点介绍图的存储结构及常用算法。,第7章 图,1、图的定义 图是由非空的有穷顶点集合V和表示顶点间关系的弧或边的有穷集合E组成的二元组，一般记为： G（V，E） 其中，V=vi | vidataobject，E=或（x，y）| vi , vjV，dataobject是具有相同性质的数据元素（即顶点）的集合； 2、有向图与无向图 有序对表示从顶点vi到vj有一条边单向相连称作弧，且称vi为弧尾（始点），vj为弧头（终点），此时称图为有向图。如图7.1（b）中的G2为有向图
3、。若E，且有E，则可以用无序对（vi , vj）代替这两个有序对，即图中的每条边都是没有方向的，则称G为无向图。如图7.1（a）中的G1为无向图。,7.1 图的基本概念,3、完全图与子图 将具有最大的边数n(n-1)2条边的无向图称为无向完全图；具有n(n-1)条弧的有向图称为有向完全图。而将具有很少条边或弧的图称为稀疏图，反之称为稠密图。假设有两个图G =（V，E）和G=（V，E），如果VV且EE，则称G为G的子图。例如，图7.2为图7.1中图G1和G2的一些子图。,4、邻接与关联 对于无向图G =（V，E），若（x，y）E，则称x和y互为邻接点，即x和y相邻接，边（x，y）依附于顶点x和y
4、，或者说边（x，y）和顶点x和y相关联。同样，对于有向图，若是一条弧，则称顶点x邻接到顶点y，顶点y邻接于顶点x，或者称弧关联于顶点x和y，也可以称弧与顶点x和y相关联。 5、度、入度和出度 在无向图中，顶点V的度是与该顶点相关联的边的数目，记为D(v)。而在有向图中要区别顶点的入度和出度的概念。入度是指以顶点V为头或终点的弧的数目，记为 ID(v)；出度是指以顶点V为尾或始点的弧的数目，记为OD(v)，并将出度为0的顶点称为终端顶点(或叶子)；顶点V的度则定义为该顶点的入度和出度之和，即D(v)ID(v)十OD(v)。,6、路径与回路 在无向图G中，若存在一个顶点序列Vp，Vi1，Vi2，V
5、in，Vq ，使得(Vp，Vi1)，(Vi1，Vi2)，(Vin，Vq)都是E中的边，或者在有向图中，若，都是E中的弧，则称Vp，Vi1，Vi2，Vin，Vq为从顶点Vp到顶点Vq的一条路径，而将该路径上边或弧的数目称为路径长度。如果在一条路径上，除了Vp和Vq相同外，其他顶点都不相同，则称此路径为一条简单路径，而将起点和终点相同（即Vp=Vq）的简单路径称为简单回路或环。 7、连通图与强连通 在无向图G中，如果从顶点Vi到Vj有路径，则称Vi和Vj是连通的。如果图G中任意两个不同的顶点Vi和Vj（即ViVj）都存在路径连通，则称该图G是连通图。 一个无向图G的极大连通子图称为此图的连通分量。
6、在有向图G中，如果对于任意两个不同的顶点Vi，Vj（即ViVj），都存在从Vi到Vj和从Vj到Vi的路径，则称该有向图G是强连通图。一个有向图G的极大强连通子图称作该有向图G的强连通分量。 例如，图7.1中的图G2不是强连通图，图7.3（a）中有两个强连通分量，分别如图7.3（b）和（c）所示。,8、网络 有时在实际应用中，图的边或弧具有与它相关的数称作权。权可以表示一个顶点到另一个顶点的距离、花费的代价等。带权的图称为网络。 9、生成树 一个连通图的生成树是一个极小连通子图，它包含有图中全部的n个顶点和n-1条边。如果在一棵生成树上添加一条边，则必定构成一个环。例如，图7.1中的G1即为其本
7、身的生成树。一个有n个顶点的连通图的生成树有且仅有n-1条边。,7.2 图的存储结构,本节讨论三种常用的图与网的存储结构：邻接矩阵、邻接表和邻接多重表。 7.2.1 邻接矩阵 1、邻接矩阵 对一个具有n个顶点的图或网，可以用一个一维数组表示其顶点信息，用邻接矩阵来表示顶点间是否相邻的关系。若G是一个具有n个顶点的图，则G的邻接矩阵A应是具有如下性质的n阶方阵:,1 (Vi，Vj) 或Vi，VjE（G） Ai，j 0 (Vi，Vj) 或Vi，VjE（G）,例如，图7.1中Gl和G2的邻接矩阵A1和A2分别为：,借助于邻接矩阵很容易判断出两个顶点是否相邻，并计算出各顶点的度。在无向图中，顶点Vi的
8、度是邻接矩阵A中第i行的非零元素个数之和，即,在有向图中，顶点Vi的出度是邻接矩阵A中第i行非零元素个数之和，而顶点Vi的入度是邻接矩阵A中第i列非零元素个数之和，即,网络的邻接矩阵A定义为：,wij (Vi，Vj) 或Vi，VjE Ai，j= (Vi，Vj) 或Vi，VjE,2、邻接矩阵表示 #define MAXVAL 99999 /* 设最大值为99999 */ #define MAXNUM 20 /*最大顶点数*/ typedef char vertextype； /* 顶点数据类型，此处设为char类型*/ typedef float adjtype； /*权值类型*/ typede
9、f struct vertextype vexMAXNUM; /*用一维数组表示顶点*/ adjtype arcsMAX NUMMAXNUM； /*邻接矩阵用二维数组表示*/ int n，e； /* 图的当前顶点数和弧或边数*/ *mgraph;,3、邻接矩阵表示法构造无向网 void creatgraph(mgraph g) /* 采用邻接矩阵表示法构造无向网g */ int i，j，k；float w； scanf(“%d %d”，&g-n，&g-e)；/* 输入图的顶点数和边数*/ for (i=1；in；i+) scanf(“%c”，&g-vexi)； /* 构造顶点向量*/ for
10、(i=1；in；i+) for (j=1；jn；j+) g-arcsij=MAXVAL；/* 初始化邻接矩阵*/ for (k=1；ke；k+) scanf(“%d %d %f”，&i，&j，&w)； g-arcsij= w； g-arcsji=w； /*权值赋予邻接矩阵的相应元素*/ /*creagraph*/,7.2.2 邻接表 1、结点结构 邻接表（Adjdcency List）是图或网的一种链式存储结构。在邻接表中，对图或网中的每个顶点建立一个单链表，单链表中的结点表示该顶点的所有邻接点。在有向图中，某顶点所对应的单链表中的结点是以该顶点为弧尾的顶点。每一个结点由三个域组成，其中，邻接
11、点域（adjvex）指示与顶点vi邻接的顶点在图中的序号，指针域（link）指示vi的下一个邻接结点，有时，可以在结点中添加信息域（info）用于存储和边或弧相关的信息，如权值等。为了能够随机访问任一个顶点的邻接链表，可以在每一个邻接链表前增设一个表头结点，然后将所有邻接表的表头结点存放在一个一维数组中。表结点和表头结点结构如下所示：,2、类型定义 表结点类型定义： #define M 50 typedef struct node int adjvex； /*邻接点域*/ struct node *link； /*指针域*/ edgenode； 表头结点类型定义： typedef struct
12、 headnode vextype vexdata； /* 顶点数据域*/ struct node *firstarc；/* 指针域指向链表中第一个结点*/ vexnode； 邻接表类型： typedef vexnode adjlistM；/* adjlist为邻接表类型*/,3、邻接表与逆邻接表 图7.5（a）给出了图7.1中无向图G1的邻接表，图7.5（b）、（c）给出了图7.1中有向图 G2的邻接表和逆邻接表。若要表示网的邻接表，则只需在链表的每个结点中增加一个存放边或弧的权值的数据域（info）即可。利用邻接表可以很容易地查找到任一个顶点的邻接点，但要判定任意两个顶点vi和vj之间是否
13、有边或弧相连，则需要搜索第i个或第j个链表，在这一点上不及邻接矩阵方便。,4、无向图的邻接表生成算法 void creatlist(vexnode ag ，int n) edgenode *p; int i，j，k；char ch； for(i=1；i adjvex =j； p-link=agi.firstarc； agi.firstarc=p； /*结点j插入到第i个链表 */ p= (edgenode *)malloc(sizeof(edgenode )；,p-adjvex =i； p-link=agj.firstarc； agj.firstarc=p；/* 结点i插入到第j个链表的头部
14、*/ scanf(“d，d”，&i，&j)； /*creatlist */,该算法的时间复杂度是O(n+e)（e为边数）。 有向图邻接表的建立算法与建立邻接矩阵的算法相似，但在输入一条弧的顶点序号时只需生成一个结点（其adjvex域为j）并将其插入到第i个顶点的链表中即可。,7.2.3 邻接多重表 1、结点结构 邻接多重表是无向图的另一种链式存储结构。在邻接多重表中，每条边用一个结点表示，每个结点由5个域组成，其结点结构如下图所示。其中，mark是标志域，可用来标记这条边是否访问过；ivex和jvex为该边依附的两个顶点vi、vj的序号；ilink指向依附于顶点vi的下一条边；jlink指向依
15、附于顶点vj的下一条边。有时，可以根据实际应用增加存放与边相关信息的域info。,而图或网中每一个顶点的结点结构由数据域(data)和指针域(firstarc)组成，数据域存放与该顶点有关的信息，指针域指示依附于该顶点的第一条边。其结点结构如下所示： 2、类型定义： typedef struct arcnode int mark，ivex，jvex； struct arcnode *ilink，*jlink； edgenode； typedef struct vexnode int data； struct arcnode *firstarc； vexnode；,图7.6 邻接多重表示例,和树
16、的遍历运算类似，图的遍历（Traversing Graph）是指从图中的任一个顶点出发访问图中所有顶点，并且使每个顶点仅被访问一次的运算。由于图结构本身的复杂性，使得图的遍历要比树的遍历复杂得多。 图的遍历是图的一种重要操作，对图的许多操作都可在遍历过程中完成，如求解图的连通性、拓扑排序和求关键路径等问题。 根据搜索路径的方向不同，通常有两种遍历图的方法：深度优先搜索遍历和广度优先搜索遍历，这两种遍历方法对无向图或有向图都适用。,7.3 图的遍历,7.3.1 深度优先搜索遍历 1、图的深度优先搜索 图的深度优先搜索（Depth First Search）遍历类似于树的前序遍历。假设给定图G的初始
