《数据结构——图课件.ppt》由会员分享，可在线阅读，更多相关《数据结构——图课件.ppt（76页珍藏版）》请在三一办公上搜索。
1、5.1 图的基本概念,图是一种重要的，比树更复杂的非线性数据结构。在树中，每个结点只与上层的父结点有联系，并可以与其下层的多个子结点有联系。但在图中，结点之间的联系是任意的，每个结点都可以与其它的结点相联系。图的应用极为广泛，特别是近年来发展迅速，已渗入到诸如语言学、逻辑学、物理、化学、电信工程、计算机、数学及其它分支中。,图的定义及相关术语,图的定义：图G由两个集合V(G)和E(G)所组成，记作G=(V,E)。其中，V(G)是图中顶点的非空有限集合，E(G)是图中边的有限集合。(2)有向图。如果图中每条边都是顶点的有序对，即每条边都用箭头表明了方向，则此图为有向图。有向图中的边也称为弧，用尖
2、括号括起一对顶点表示。,有向图示例,图中所示的G1为有向图，它由V(G1)和E(G1)组成。V(G1)=V1，V2，V3，V4E(G1)=，如其中弧，称V1为初始点或弧之尾，V2为终端点或弧之头。,(3)无向图。如果图中每条边都是顶点的无序对，则称此图为无向图。无向边用圆括号括起的两个相关顶点来表示。如图所示的G2为无向图。V(G2)=V1，V2，V3，V4E(G2)=(V1,V2)，(V1,V3)，(V3,V4)，(V4,V1)注意，在无向图中，(V1,V2)与(V2,V1)表示同一条边。,图3-23 无向图示例,(4)子图。设有两个图GA和GB，且满足 V(GB)V(GA)E(GB)E(G
3、A)则称GB是GA的子图。如下图所示。,图与子图,(5)带权图。在图的边或弧上加上一个相关联的数(权)，称为带权图或网。如下图所示。,A,B,E,C,F,15,9,7,21,11,3,2,有向网,无向网,(6)完全图。假设图中有 n 个顶点，e 条边，则含有 e=n(n-1)/2 条边的无向图称作完全图；含有 e=n(n-1)条弧的有向图称作有向完全图。(7)稠密图与稀疏图。若图的边或弧的数目接近于相应完全图的边或弧的数目，则称之为稠密图，否则称为稀疏图。,(8)路径。在一个图中，如果从顶点V1出发，沿着一些边经过顶点V1，V2，Vn-1到达顶点Vn，则称顶点序列(V1，V2，Vn-1，Vn)
4、为从V1到Vn的一条路径。路径上边(弧)的数目称为该路径的长度。例如：下图中，A,B,C,F的路径长度为3。,(9)简单路径：序列中顶点不重复出现的路径。,(10)简单回路：序列中第一个顶点和最后一个顶点相同的简单路径。(11)连通图：在无向图中，若每一对顶点之间都有路径，则称此图为连通图。(12)连通分量：若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。,连通图,B,A,C,D,F,E,B,A,C,D,F,E,非连通图,(13)强连通图：在有向图中，若每一对顶点u和v之间都存在v到u及u到v的路径，则称此图为强连通图。(14)强连通分量：各个强连通子图称作该有向图的强连通分量。
5、,强连通图,非强连通图,(15)邻接点。在无向图中，如果边(u,v)E，则u和v互为邻结点，即u是v的邻结点，v也是u的邻结点。边(v,w)与顶点u 和v相关联。在有向图中，如果弧E，则v是u的邻结点。称u邻接到v，或顶点v邻接自顶点u。(16)顶点的度。在无向图中，顶点的度就是和该顶点相关联的边的数目，记为TD(V)。在有向图中，以某顶点为弧头的弧的数目，称为此顶点的入度，记作ID(V)；以某顶点为弧尾的弧的数目称为此顶点的出度，记作OD(V)。该顶点的度则是此顶点的入度与出度之和。,A,C,D,F,E,TD(B)=3，TD(A)=2,B,A,B,E,C,F,ID(B)=2，OD(B)=1,
6、TD(B)=ID(B)+OD(B)=3,建立和销毁图结构,插入或删除顶点,对邻接点的操作,访问顶点,遍历图,插入和删除弧,基本操作,5.2 图的存储结构,图的存储结构,一、图的数组(邻接矩阵)存储表示,二、图的邻接表存储表示,*三、有向图的十字链表存储表示,*四、无向图的邻接多重表存储表示,根据图的定义可知，一个图的逻辑结构分两部分，一部分是组成图的顶点的集合；另一部分是顶点之间的联系，即边或弧的集合。可用一个一维数组存放图中所有顶点的信息；用一个二维数组来存放数据元素之间的关系的信息(即边或弧的集合E)。这个二维数组称之为邻接矩阵。邻接矩阵是表示顶点之间的邻接关系的矩阵。设G=(V，E)是有
7、n(n1)个顶点的图，则G的邻接矩阵A是一个nn阶矩阵。,Aij=,0 若(Vi,Vj)或E(G),1 若(Vi,Vj)或E(G),一、图的数组(邻接矩阵)存储表示,定义:矩阵的元素为,A,B,C,D,E,F,A,B,C,D,E,F,有向图的邻接矩阵,A,B,C,D,E,在一般情况下，我们不关心图中顶点的情况，若将顶点编号为1Vtxnum，设弧上或边上无权值，则图的存储结构可以简化为用一个二维数组表示：int adjmatrixVtxnumVtxnum；,特点,无向图的邻接矩阵是对称的;有向图的邻接矩阵不一定对称。对于无向图，邻接矩阵第i行(或第i列)的元素之和是顶点Vi的度。对于有向图，邻接
8、矩阵第i行元素之和为顶点Vi的出度；第i列的元素之和为顶点Vi的入度。使用邻接矩阵法容易判断任意两个点的邻接关系。,网的邻接矩阵可定义为,若,或,其中Wij是边(Vi,Vj)或弧上的权值。,邻接表是一种顺序分配和链式分配相结合的存储结构。它包括两个部分：一部分是链表；另一部分是向量。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点包含了顶点Vi的所有邻接顶点。每个结点由三个域组成：adjvex、data和nextarc，如下图所示。,二、图的邻接表存储表示,邻接表中表结点的结点结构,顶点Vi的邻接点在图中的位置,指向顶点Vi的下一邻接点的指针,为便于邻接表操作，在每个单链表上附设
9、一个头结点，在头结点中有两个域：vexdata和firstarc。如下图所示。,邻接表中头结点的结点结构,指向顶点Vi的第一个邻接点的指针,存储Vi的名字或有关信息,为了利用顺序存储结构的随机访问特性，邻接表中将每个单链表的头结点以顺序结构的形式存储，以便能随机访问任一顶点的单链表。邻接表的存储结构可以用C语言描述如下：#define VTXUNMn/*n为图中顶点个数的最大可能值*/,struct arcnode int adjvex;float data;struct arcnode*nextarc;typedef struct arcnode ARCNODE;struct headnod
10、e int vexdata;ARCNODE*firstarc;adjlistVTXUNM;,0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3,示例：无向图的邻接表,有向图的邻接表,在有向图的邻接表中不易找到指向该顶点的弧，即难以确定某个顶点的入度。,有向图的逆邻接表,在有向图的逆邻接表中，每个顶点链接的是指向该顶点的弧。,有向带权图的邻接表,在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点(Vi和Vj)之间是否有边或弧相连，则需搜索第i个或第j个链表，因此不及邻接矩阵方便。对一个图来说，邻接表不是惟一的，它取决于建立邻接表
11、时，结点在每个单链表中的插入策略。另外，对于有向图，其邻接表中第i个单链表的结点个数就是此结点的出度；对于无向图，其邻接表中第i个单链表的结点个数就是此结点的度。,5.3 图的遍历,图的遍历,从图中某个顶点出发访问图中每个顶点一次且仅一次的过程。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。,深度优先搜索,广度优先搜索,从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图中的其余顶点，直至图中所有和V0有路径相通的顶点都被访问到为止。,一、深度优先搜索遍历图,连通图的深度优先搜索遍历(用栈),W1、W2和W3 均为 V0 的邻接
12、点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。,访问顶点 V0：for(W1、W2、W3)若该邻接点Wi未被访问过，则从它出发进行深度优先搜索遍历。,算法分析,1.深度优先搜索遍历连通图的过程类似于树的先根遍历；,解决的办法：设立一个一维数组，用来记录每个顶点是否被访问过，即“访问标志 visitedw”。,2.如何判别V0的邻接点是否被访问？,显然，这个遍历过程是个递归过程。在设计具体算法时，首先要确定图的存储结构，下面以邻接表为例，讨论深度优先搜索法。例 连通图G的邻接表表示如下图所示，以顶点V1为始点，按深度优先搜索遍历图中所有顶点，写出顶点的遍历序列。,连通图G
13、及其邻接表,解：先访问V1，再访问与V1邻接的V2，再访问V2的第一个邻接点，因V1已被访问过，则访问V2的下一个邻接点V4，然后依次访问V8，V5。这时，与V5相邻接的顶点均已被访问，于是反向回到V8去访问与V8相邻接且尚未被访问的V6，接着访问V3，V7，至此，全部顶点均被访问。相应的访问序列为：V1V2V4V8V5V6V3V7。,下面给出dfs的递归算法。#define VTXUNMn/*n为图中顶点个数的最大可能值*/struct arcnode int adjvex;float data;struct arcnode*nextarc;,typedef struct arcnode A
14、RCNODE;struct headnode int vexdata;ARCNODE*firstarc;struct headnode GVTXUNM+1;int visitedVTXUNM+1;,void dfs(struct headnode G,int v)ARCNODE*p;printf(%d-,Gv.vexdata);visitedv=1;p=Gv.firstarc;while(p!=NULL)/*当邻接点存在时*/if(visitedp-adjvex=0)dfs(G,p-adjvex);,p=p-nextarc;/*找下一邻接点*/void traver(struct headno
15、de G)int v;for(v=1;v=VTXUNM;v+)visitedv=0;for(v=1;v=VTXUNM;v+)if visitedv=0 dfs(G,v);,首先将图中每个顶点的访问标志设为 FALSE,随后搜索图中每个顶点，如果未被访问过，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一个顶点。非连通图的深度优先搜索遍历需多次调用dfs算法。每调用一次dfs得到的顶点集合恰为图中一个连通分量的顶点集合，这些顶点集合中的顶点加上所有依附于这些顶点的边，便构成了非连通图的一个连通分量。,非连通图的深度优先搜索遍历,F F F F F F F F F,T,T,T,T,T,T
16、,T,T,T,a,c,h,d,k,f,e,b,g,访问标志:,访问次序:,例如:,0 1 2 3 4 5 6 7 8,0,1,6,2,3,4,5,7,8,二、广度优先搜索遍历图,对连通图，从起始点v到其余各顶点必定存在路径。,其中，vw1,v w2,v w8 的路径长度为1；,v w7,v w3,v w5 的路径长度为2；,v w6,v w4 的路径长度为3。,从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，随后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有与V0有路径相通的顶点都被访问到为止。,连通图的广度优先搜索遍历,例 对图示连通图G，从顶
17、点V1出发，写出顶点的广度优先遍历序列。解：按广度优先搜索法从V1开始遍历，访问V1，然后访问V1的邻接点V2，V3，再依次访问V2和V3的未曾被访问的邻接点V4，V5及V6，V7，最后访问V4的邻接点V8。遍历序列如下：V1V2V3V4V5V6V7V8,连通图G及其邻接表,注意，在bfs算法中，若W1在W2之前访问，则W1的邻接点也将在W2的邻接点之前访问，这里蕴涵了一个排队关系。在实现算法时，需设一个队列，每访问一个顶点后将其入队，然后将队头顶点出列，去访问与它邻接的所有顶点，重复上述过程，直至队空为止。下面给出bfs的相应算法。,广度优先遍历算法。#define VTXUNMnvoid
18、bfs(struct headnode G,int v)int queueVTXUNM;int rear=VTXUNM1,front=VTXUNM1;int i;ARCNODE*p;printf(%d-,Gv.vexdata);,visitedv=1;rear=(rear+1)%VTXUNM;queuerear=v;/*访问过的顶点进队列*/while(rear!=front)front=(front+1)%VTXUNM;v=queuefront;p=Gv.firstarc;while(p!=NULL)if(visitedp-adjvex=0),printf(%d-,Gp-adjvex.vex
19、data);visitedp-adjvex=1;rear=(rear+1)%VTXUNM;queuerear=p-adjvex;p=p-nextarc;,若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。非连通图的广度优先搜索遍历需多次调用bfs算法。每调用一次bfs得到的顶点集合恰为图中一个连通分量的顶点集合，这些顶点集合中的顶点加上所有依附于这些顶点的边，便构成了非连通图的一个连通分量。,非连通图的广度优先搜索遍历,5.4 图的应用,生成树：若图是连通图，从图中的某一个顶点出发进行遍历时，可以系统地访问图中所有顶点，此时图中所
20、有的顶点加上遍历时经过的边所构成的子图，称为连通图的生成树。并且称由深度优先搜索得到的生成树为深度优先生成树；由广度优先搜索得到的生成树为广度优先生成树。例如，下面的图示分别为连通图G的深度优先生成树和广度优先生成树。,生成树的概念,连通图G及其邻接表,连通图G从V1出发的两种生成树(a)深度优先生成树；(b)广度优先生成树,有n个顶点的连通图，其生成树有n1条边；生成树中不含回路；生成树不是惟一的，因为起点不同，访问的路径也不同。对于非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林。,生成树可以解决一些实际问题。如要建n个城市之
21、间的通信联络网，则连通n个城市只需n1条线路。若以n个城市做图的顶点，n1条线路做图的边，则该图的生成树就是可行的建造方案。每条线路建造需付出一定代价(相当于边上的权)，那么对n个顶点的连通网可以建立许多不同的生成树，每棵生成树都可以是一个通信网，我们当然希望选择一个总耗费最小的生成树，即最小代价生成树。,最小生成树：生成树各边上的代价之和，称为生成树的代价，使代价最小的生成树，称为最小代价生成树，简称最小生成树。那么上述通信网的问题就转化为求最小生成树的问题。例如，下图中图(a)是个连通网，它的最小生成树如图(b)所示。,连通网及其最小生成树(a)无向连通网；(b)最小生成树,构造最小生成树
22、的原则：(1)尽可能选权值小的边，但不构成回路。(2)在网中选n1条边以连接网中的n个顶点。通常求最小生成树的算法有两种：普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。,两顶点之间的最短路径问题,求从某个源点到其余各顶点的最短路径,每一对顶点之间的最短路径(略),迪杰斯特拉算法是著名的求解最短路径的算法。,求从源点到其余各点的最短路径的算法的基本思想:,依最短路径的长度递增的次序求得各条路径。,源点,v1,其中，从源点到顶点v的最短路径是指从源点到v的所有路径中权值之和最小的那条路径。,v2,v1:无v0v2:10v0 v4 v3:50v0 v4:30v0 v4 v3 v5:60,在这条路径上，必定只含一条弧，并且这条弧的权值最小。,下一条路径长度次短的路径为：,路径长度上第一条最短路径为：,它只可能有两种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。,其余最短路径的特点：,再下一条路径长度次短的路径为:,可能有三种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。,或者是直接从源点到该点(只含一条弧)；或者是从源点经过已求得最短路径的顶点，再到达该顶点。,习 题,P122 一(114)、二(111)、三(15),
