《《数据结构》课件》由会员分享，可在线阅读，更多相关《《数据结构》课件（110页珍藏版）》请在金锄头文库上搜索。
1、第7章 图,数据结构（C描述）,目录,7.1 图的基本概念,7.2 图的存储结构,7.3 图的遍历,7.4 图的生成树和最小生成树,7.5 图的应用,7.1 图的基本概念,图(Graph)是一种比线性表和树结构更复杂的数据结构。,在线性表中，数据元素之间仅有线性关系，每 个数据元素只有一个直接前驱和直接后继； 在树形结构中，数据元素之间有着明显的层次 关系结点间具有分支层次关系，每一层上的结 点只能和上一层中的至多一个结点相关，但可 能和下一层的多个结点相关。,而在图状结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。因此，图状结构被用于描述各种复杂的数据对象，在自然科学、
2、社会科学和人文科学等许多领域有着非常广泛的应用。,7.1.1 图的定义,图(Graph)是由非空的顶点集合和一个描述顶点之间关系的边（或者弧）的集合组成，其形式化定义为： G（V，E） Vvi| viVertexType E( vi,vj)| vi,vj V 其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合，集合E中(vi,vj)表示顶点vi和顶点vj之间有一条直接连线，即偶对(vi,vj)表示一条边。,无向图G1,有向图G2,例如：对于下图中的无向图G1,对应顶点集和边集为： V(G1)v1,v2,v3,v4,v5； E(G1)(v1,v2),(v1,v4),(v2,v3),(v
3、3,v4),(v3,v5),(v2,v5) 对于下图中的有向图G2,对应顶点集和边集为： V(G2)v1,v2,v3,v4,v5； E(G2), , , , , , ,7.1.2 图的基本术语,有向图和无向图 完全图、稠密图、稀疏图 度、入度、出度 子图 路径 连通图 权和网,7.2 图的存储结构,图是一种结构复杂的数据结构，表现在不仅各个顶点的度可以千差万别，而且顶点之间的逻辑关系也错综复杂。从图的定义可知，一个图的信息包括两部分，即图中顶点的信息以及描述顶点之间的关系（边或者弧）的信息。因此无论采用什么方法建立图的存储结构，都要完整、准确地反映这两方面的信息。 下面介绍几种常用的图的存储结
4、构。,7.2.1 邻接矩阵,1 图的邻接矩阵表示,在邻接矩阵表示中，除了存放顶点本身信息外，还用一个矩阵表示各个顶点之间的关系。若（i,j）E(G)或i,jE(G),则矩阵中第i行第j列元素值为1，否则为0 。,图的邻接矩阵定义为： 1 若（i,j）E(G)或i,jE(G) Aij= 0 其它情形,例如, 对图7-8所示的无向图和有向图,它们的邻接矩阵见图7-9。,无向图,G3,G3的邻接矩阵,图,7,-,9,邻接矩阵表示,有向图,G4,G4,的邻接矩,图,7,-,9,邻接矩阵表示,2 从无向图的邻接矩阵可以得出如下结论,（1）矩阵是对称的; （2）第i行或第i 列1的个数为顶点i 的度; （
5、3）矩阵中1的个数的一半为图中边的数目; （4）很容易判断顶点i 和顶点j之间是否有边相连(看矩阵中i行j列值是否为1)。,3 从有向图的邻接矩阵可以得出如下结论,（1） 矩阵不一定是对称的; （2） 第i 行中1的个数为顶点i 的出度; （3） 第i列中1的个数为顶点 i的入度; （4） 矩阵中1的个数为图中弧的数目; （5） 很容易判断顶点i 和顶点j 是否有弧相连.,4 网的邻接矩阵表示,类似地可以定义网的邻接矩阵为： wij 若（i,j）E(G)或i,jE(G) Aij= 0 若i=j 其它情形,网及网的邻接矩阵见图7-10。,图,7,-,10,网及邻接矩阵示意图,(a)网G5,(b)
6、网G5的邻接矩阵,3 图的邻接矩阵数据类型描述,用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要用一个顺序表来存储顶点信息。其形式说明如下：,# define n 6 / * 图的顶点数 * / # define e 8 / * 图的边（弧）数 */ typedef char vextype； / * 顶点的数据类型 * / typedef float adjtype； / * 权值类型 * / typedef struct vextype vexsn； adjtype arcsnn； graph；,4 建立无向图的邻接矩阵,void creatadj(graph
7、 /初始化邻接矩阵,for (k=1; k=e; k+) scanf(“d%d”, 该算法的时间复杂度为O（n2）。,5.建立有向图的邻接矩阵,void creatadj(graph /初始化邻接矩阵,for (k=1; k g.arcsij=1; 该算法的时间复杂度为O（n2）。,6.建立无向网的邻接矩阵,void creatadj(graph /初始化邻接矩阵,for (k=1; k=e; k+) scanf(“%d%d%f”, 该算法的时间复杂度为O（n2）。,7.建立有向网的邻接矩阵,void creatadj(graph /初始化邻接矩阵,for (k=1; k 及权值w g.arc
8、sij=w; 该算法的时间复杂度为O（n2）。,7.2.2 邻接表,1 图的邻接表表示,将每个结点的边用一个单链表链接起来，若干个结点可以得到若干个单链表，每个单链表都有一个头结点，所有头结点组成一个一维数组，称这样的链表为邻接表。 例如，图7-8所示的无向图G3和有向图G4的邻接表见图7-11所示,(,(b),有向图,G4,的邻接表,(c),有向图,G4,的逆邻接表,图,7,-,11,邻接表示例,有向图,G4,(a)无向图G3,(b)无向图G3的邻接表,图711：邻接表示例,图711：邻接表示例,(a)有向图G4,(b)有向图G4的邻接表,(c)有向图G4的逆邻接表,1 从无向图的邻接表可以
9、得到如下结论,（1）第i 个链表中结点数目为顶点i的度； （2）所有链表中结点数目的一半为图中边数； （3）占用的存储单元数目为n+2e 。,2 从有向图的邻接表可以得到如下结论,（1）第i 个链表中结点数目为顶点i的出度； （2）所有链表中结点数目为图中弧数； （3）占用的存储单元数目为n+e 。,从有向图的邻接表可知，不能求出顶点的入度。为此，我们必须另外建立有向图的逆邻接表，以便求出每一个顶点的入度。逆邻接表在图7-11(c)中已经给出，从该图中可知。有向图的逆邻接表与邻接表类似，只是它是从入度考虑结点，而不是从出度考虑结点。,3 图的邻接表数据类型描述,图的邻接表数据类型描述如下： c
10、onst int n =maxn； / maxn表示图中最大顶点数 const int e= maxe ； / maxe图中最大边数 struct link /定义链表类型 elemtype data ; link *next ; ; struct node /定义邻接表的表头类型 elemtype v; /顶点信息 link *next; an+1;,4.无向图的邻接表建立,void creatlink( ) int i, j, k ; link *s ; for(i=1; idata=j ; s-next=ai.next ;ai.next=s ;,s= (link * ) malloc (
11、sizeof(link); s-data=i ; s-next=aj.next ;aj.next=s ; 该算法的时间复杂度为O（n+e）。,5.有向图的邻接表建立,void creatlink( ) int i, j, k ; link *s ; for(i=1; i,s=(link * ) malloc (sizeof(link); /申请一个动态存储单元 sdata=j ;s-next=ai.next ; ai.next=s ; 该算法的时间复杂度为O（n+e）。,6.网的邻接表的数据类型描述,网的邻接表的数据类型可描述如下： const int n =maxn； / maxn表示网中最
12、大顶点数 const int e= maxe ； / maxe网中最大边数 struct link /定义链表类型 elemtype data ; float w; /定义网上的权值类型为浮点型 link *next ; ; struct node /定义邻接表的表头类型 elemtype v; /顶点信息 link *next; an+1;,7 无向网的邻接表建立,void creatlink( ) float w; int i,j,k ; link *s ; for(i=1; i=n;i+) /建立邻接表头结点 ai.v=i ; ai.next=NULL; for(k=1; k=e;k+)
13、 scanf(“%d%d%d”, /输入一条边 (i,j)及该边上的权值,s=(link *) malloc (sizeof (link); /申请一个动态存储单元 sdata=j ;s-w=w; s-next=ai.next ;ai.next=s ; s= (link *) malloc (sizeof (link); s-data=i;s-w=w;snext=aj.next ;aj.next=s ; 该算法的时间复杂度为O（n+e）。,8 有向网的邻接表建立,void creatlink( ) float w;int i,j,k ; link *s ; for(i=1; i及该弧上的权值,
14、s=(link *) malloc (sizeof (link); /申请一个动态存储单元 sdata=j ;s-w=w; s-next=ai.next ; ai.next=s ; 该算法的时间复杂度为O（n+e）。,另外，请注意上面的算法中，建立的邻接表不是唯一的,与你从键盘输入边的顺序有关，输入的边的顺序不同，则得到的链表也不同。,7.2.3 邻接多重表,在无向图的邻接表中，每条边（Vi,Vj）由两个结点表示，一个结点在第i个链表中，另一个结点在第j个链表中，当需要对边进行操作时，就需要找到表示同一条边的两个结点，这给操作带来不便，在这种情况下采用邻接多重表较方便。 在邻接多重表中，每条边用一个结点表示，每个结点由五个域组成，其结点结构为 ：,其中mark为标志域，用来标记这条边是否被访问过，i和j域为一条边的两个顶点，next1 和next2为两个指针域，分别指向依附于i顶点的下一条边和j顶点的下一条边。而表头与邻接表的表头类似。 邻接多重表的形式见图7-12。,(a),无向图,G6,（,b,）,G6,的邻接多重表,图,7,-,12,邻接多重表示例,7.3 图的遍历,
