数据结构六章图ppt课件

1、第六章 图6.1 图的概念图(Graph)是一种结点之间为多对多关系的数据构造。逻辑特征是：可以有恣意个开场结点和恣意个终端结点，其他各个结点可以有恣意个前趋和恣意个后继。图中的结点常称为顶点。图的逻辑构造可以用二元组表示： Graph(V,E) V是顶点(vertex)的集合； E是边(edge)的集合。v有向图有向图(Digraph)假设图假设图G中的每条边都是有中的每条边都是有方向的，那么称图方向的，那么称图G为有向图。为有向图。例 G1 = (V1, E1)V1 = v1, v2, v3E1 = , , G2 = (V2, E2)V2 = v1, v2, v3E2 = , , , ,

2、, v无向图无向图(Undigraph)假设图假设图G中的每条边都是没中的每条边都是没有方向的，那么图有方向的，那么图G称为无向图。称为无向图。例 G3 = (V3, E3)V3= v1, v2, v3, v4E3= (v1, v2), (v1, v3), (v1, v4), (v2, v3), (v2, v4)G4 = (V4, E4)V4= v1, v2, v3 E4= (v1, v2), (v1, v3), (v2, v3) v顶点的度v有向图中，顶点的度分成入度与出度v入度：该顶点入边的数目v出度：该顶点出边的数目v无向图中，顶点的度为与该顶点相连的边数v邻接点与关联边v有向图中，假设

3、是有向图中的一条边，那么顶点xv 和顶点y称为邻接点。称x邻接到y或y邻v 接于x，同时称边是顶点x和顶点yv 相关联的边Incident； v无向图中，假设x,y是无向图中的一条边，那么顶点v x和顶点y互为邻接点,并且称边(x, y)是v 顶点 x和顶点y相关联的边。v子图设有图G=(V,E) ，假设满足：vVVvEEvE中边所邻接的点均在V中出现v 那么 G= (V,E)也是一个图，并且称之为G的子图。v有向完全图n个顶点的有向图最大边数是n(n-1)v无向完全图n个顶点的无向图最大边数是n(n-1)/2v途径有向图G=(V,E)中，假设存在一个顶点序列vp,vi1,vi2,vin,vq

4、，使得,均是图中的边，那么称此序列是从顶点vp到vq一条途径。v途径长度该途径上经过边的数目。v回路一条途径第一个顶点和最后一个顶点一样的 叫v简单途径序列中顶点不反复出现的途径叫v简单回路除了第一个顶点和最后一个顶点外，其他顶点不反复出现的回路叫v有根图假设存在一个顶点v，从该顶点到其他各个顶点都有途径，那么称此图为有根图 v连通从顶点x到顶点y有一条途径，那么说x和y是连通的v连通图图中恣意两个顶点都是连通的叫连通图v连通分量无向图G的极大连通子图称为G的连通分量 v强连通图假设G中恣意两个顶点都是强连通的，那么称图G是强连通图 v强连通分量 有向图G的极大强连通子图称为G的强连通分量 v

5、权与图的边相关的数值叫权值。v网络边上带权的图称为网络 6.2 图的存储构造邻接矩阵表示顶点之间邻接关系的矩阵 设G=(V,E是具有n个顶点的图，那么G的邻接矩阵是一个n阶方阵A，A中元素的值aij可以定义为： v特点：v无向图的邻接矩阵对称；有n个顶点的无向图需存储空间为n 有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为nv无向图中顶点Vi的度是邻接矩阵A中第i行元素之和v有向图中，v顶点Vi的出度是A中第i行元素之和v顶点Vi的入度是A中第i列元素之和v网的邻接矩阵可定义为：可以得到邻接矩阵存储构造C言语描画如下：#define n 5/* 图的顶点数 */#define e 6

6、/* 图的边数 */#define max 10000/* 设置一个极大数无穷大 */typedef char vextype; /* 顶点类型 */typedef int adjtype;/* 权值类型 */typedef struct vextype vertexn+1;/* 顶点数组 */adjtype edgen+1n+1;/* 邻接矩阵 */adj_matrix;邻接表邻接表法(Adjacency List)是图的一种链式存储构造 顶点采用顺序方式进展存储，用n个单链表来存储图中的边，第i个单链表是一切与第i个顶点相关联的边链接而成的，称此单链表为第i个顶点的边表，边表中的每个结点称

7、为边表结点。在顶点的顺序表中，每个元素添加一个指针域用来存放各个边表的头指针，称此顺序表为顶点表，而顺序表中的每个元素称为顶点表结点。顶点表和各顶点的边表一同组成图的邻接表。 邻接表存储构造C言语描画如下：typedef struct node int adjvex; /* 邻接点域 */ struct node *next; /* 指针域 */edgenode; /* 定义边表结点 */typedef struct vextype vertex; /* 顶点域 */ edgenode *link; /* 指针域 */vexnode; /* 定义顶点表结点 */vexnode adjlistn

8、+1;v特点v无向图中顶点Vi的度为第i个单链表中的结点数v有向图中v顶点Vi的出度为第i个单链表中的结点个数v顶点Vi的入度为整个单链表中邻接点域值是i的结点个数v逆邻接表：有向图中对每个结点建立以Vi终点的单链表边集数组边集数组(edgeset array)(edgeset array)是图的一种顺序存储方式，利用一维数组是图的一种顺序存储方式，利用一维数组来存储图中一切的边，数组中的每个元素用来存储图中的一条边，包来存储图中一切的边，数组中的每个元素用来存储图中的一条边，包括：始点、终点的序号及权值，该数组中所含元素的个数要大于等于括：始点、终点的序号及权值，该数组中所含元素的个数要大于

9、等于图中边的条数。图中边的条数。 边集数组邻接表法(Adjacency List)是图的一种链式存储构造 typedef struct edge int fromvex; /* 边的始点域 */int endvex; /* 边的终点域 */int weight; /* 边的权值域 */edgeset; /* 定义边集数组类型 */edgeset gee+1; /* 边集数组全局量 */ 6.3 图的遍历深度优先遍历(DFS)方法：对于给定的图G，假设初始时一切顶点均未被访问过，那么可从G中任选一顶点vi做为初始出发点，深度优先搜索可定义为：访问出发点vi，置访问标志为1，然后依次从vi的未被访

10、问过的邻接点vj出发，继续进展深度优先搜索，直至图中一切和vi有途径相通的顶点均被访问过。很显然图的深度优先搜索过程是递归的。它的特点是尽能够先对图从纵深方向进展搜索，故称为深度优先搜索。 DFS序列为：v1，v2，v4，v8，v5，v3，v6，v7。 v深度优先遍历算法v递归算法void DFS(int i) int j;printf (输出序号为输出序号为%d的顶点的顶点: %cn,i,adj-vertexi); visitedi=1; /* 标志标志vi曾经访问过曾经访问过 */for (j=1;jedgeij)&(!visitedj)DFS(j);void DFSL(int i) ed

11、genode *p; printf(输出序号为%d的顶点: %cn,i,adjlisti.vertex); visited i=1; /* 标志vi曾经访问过 */ p=adjlisti; /* p为vi的边表头指针 */ while (p) /* 依次搜索vi的邻接点 */ if(!visitedp-adjvex) DFSL(p-adjvex); p=p-next; 在邻接矩阵上实现遍历的过程： 生成树连通图G的一个子图假设是一棵包含G的一切顶点的树，那么该子图称为G的生成树(Spanning Tree) 。广度优先遍历(BFS)方法：对于给定图G，假设初始时的一切顶点均未被访问过，从图G中

12、任选一顶点vi为初始出发点，广度优先搜索遍历可定义为：首先访问出发点vi，接着依次访问vi的一切的邻接的未被访问过的点w1， w2, wt，然后，再依次访问与w1，w2,wt相邻接的未被访问过的顶点。依此类推，直至图中一切和初始出发点vi有途径相通的顶点都已访问到为止。显然，此方法的特点是尽能够先对横向进展搜索，故称之为广度优先搜索。 BFS序列为：v1，v2，v3，v4，v5，v6，v7，v8 v广度优先遍历算法 在广度优先遍历中，先被访问的顶点，其邻接点亦先被访问，所以在算法的实现中需求运用一个队列，用来依次记住被访问过的顶点。 算法开场时，将初始点Vi访问后插入队列中，以后每从队列中删除

13、一个元素，就依次访问它的每一个未被访问过的邻接点，并令其进队。这样当队列为空时，阐明一切与初始点有途径相通的顶点都已访问终了，算法到此终了。例1423512341342adjvexnext 5 5 4 3adjvex next55 1 5 1 1 4 3 2 20 1 2 3 4 51fr遍历序列：10 1 2 3 4 54fr遍历序列：1 40 1 2 3 4 54 3fr遍历序列：1 4 3例1423512341342adjvexnext 5 5 4 3adjvex next55 1 5 1 1 4 3 2 20 1 2 3 4 54 3 2fr遍历序列：1 4 3 20 1 2 3 4

14、5 3 2fr遍历序列：1 4 3 20 1 2 3 4 5 3 2 5fr遍历序列：1 4 3 2 50 1 2 3 4 5 2 5fr遍历序列：1 4 3 2 50 1 2 3 4 5 5fr遍历序列：1 4 3 2 50 1 2 3 4 5 fr遍历序列：1 4 3 2 5例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 2邻接表法广度优先：邻接表法广度优先：void BFSL(int k) /* 用用adjlist存储存储 */ int i;edgenode *p;SETNULL(Q);printf(输出

15、序号为输出序号为%d的顶点的顶点: %cn,k,adjlistk.vertex); /* 访问出发点访问出发点vk */visitedk=1; /* 标志标志vk曾经访问过曾经访问过 */ENQUEUE (Q,k); /* 顶点顶点vk的序号的序号k入队入队 */while(!EMPTY(Q) /* 队列非空执行队列非空执行 */ i= DEQUEUE(Q);/* 队头元素顶点序号出队队头元素顶点序号出队 */p=adjlisti;while (p!=NULL) if(!visitedp-adjvex) printf(输出序号为输出序号为%d的顶点的顶点: %cn,p-adjvex,adjli

16、stp-adjvex.vertex);visitedp-adjvex =1;ENQUEUE(Q,p-adjvex);p=p-next;深度优先生成树与广度优先生成树阐明一个图可以有许多棵不同的生成树一切生成树具有以下共同特点：生成树的顶点个数与图的顶点个数一样生成树是图的极小连通子图一个有n个顶点的连通图的生成树有n-1条边生成树中恣意两个顶点间的途径是独一的在生成树中再加一条边必然构成回路含n个顶点n-1条边的图不一定是生成树生成树连通图G的一个子图假设是一棵包含G的一切顶点的树，那么该子图称为G的生成树(Spanning Tree) 。6.4最小生成树问题提出要在n个城市间建立通讯联络网，

17、顶点表示城市权城市间建立通讯线路所需破费代价希望找到一棵生成树，它的每条边上的权值之和即建立该通讯网所需破费的总代价最小最小代价生成树v问题分析1654327131791812752410n个城市间，最多可设置n(n-1)/2条线路n个城市间建立通讯网，只需n-1条线路问题转化为：如何在能够的线路中选择n-1条，能把 一切城市顶点均连起来，且总耗费 各边权值之和最小v定义：连通网络的一切生成树中边上权值之和最小的生成树称为最小生成树Minimun Spanning Tree) MST性质：性质： 假设假设G=(V, E)是一个连通网络，是一个连通网络，U为顶点集为顶点集V的一个非空子集。假设边

18、的一个非空子集。假设边(u,v)是一切的一个是一切的一个端点在端点在U中即中即uU，另一个端点不在，另一个端点不在U中即中即vV-U的这些边里面，权值最小的的这些边里面，权值最小的一条，那么一定存在一棵一条，那么一定存在一棵G的最小生成树包的最小生成树包括此边括此边(u,v)。 v构造最小生成树方法v方法一：普里姆(Prim)算法v算法思想：设G=(V, E)是连通网，T=U，TE是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。v初始令U=u0,(u0V), TE=v在一切uU,vV-U的边(u,v)E中，找一条代价最小的边(u0,v0)v将(u0,v0)并入集合

19、TE，同时v0并入Uv反复上述操作直至U=V为止，那么T=(V,TE)为G的最小生成树用Prim算法构造最小生成树的过程 生成树T的边集数组数组变化过程l方法二：克鲁斯卡尔(Kruskal)算法l算法思想：设连通网G=(V,E)，令最小生成树T=(U,TE)l初始形状U=V,TE=l将图G中的边按权值从小到大的顺序依次选取，假设选取的边使生成树T不构成回路，那么把它并入TE中，保管作为T的一条边；假设选取的边使生成树T构成回路，那么将其舍弃。l依此类推，直至TE中包含n-1条边为止，此时的T 即为最小生成树。用Kruskal算法构造最小生成树的过程 7.5 拓扑排序问题提出：学生选修课程问题顶

20、点表示课程有向边表示先决条件，假设课程i是课程j的先决条件，那么图中有边学生应按怎样的顺序学习这些课程，才干无矛盾、顺利地完成学业拓扑排序定义AOV网用顶点表示活动，用有向边表示活动的先后关系的有向图称为顶点活动网(Activity On Vertex network)，简称AOV网假设是图中有向边，那么vi是vj的直接前驱；vj是vi的直接后继AOV网中不允许有回路65 最短路经最短路经最短途径问题通常是指如何从图中某一顶点最短途径问题通常是指如何从图中某一顶点(称为源点称为源点)到达另一顶点到达另一顶点(称为终点称为终点)的多条途的多条途径中，找到一条途径，使得此途径上经过的径中，找到一条

21、途径，使得此途径上经过的各边上的权值总和到达最小。各边上的权值总和到达最小。最短途径问题通常可以分成四种不同情况最短途径问题通常可以分成四种不同情况: 单源点、单目的点最短途径问题；单源点、单目的点最短途径问题；单源点、多目的点最短途径问题；单源点、多目的点最短途径问题；多源点、单目的点最短途径问题；多源点、单目的点最短途径问题；多源点、多目的点最短途径问题。多源点、多目的点最短途径问题。我们讨论最常见的两种情况：单源点最短途我们讨论最常见的两种情况：单源点最短途径和恣意两点间的最短途径。径和恣意两点间的最短途径。 单源最短路经 从源点1到其他各顶点的最短途径 迪杰斯特拉迪杰斯特拉Dijkst

22、ra算法：算法： 初始化：集合初始化：集合S中只需一个源点，其他顶点都在集合中只需一个源点，其他顶点都在集合V-S中。此时中。此时S中源点的间隔值最短途径为中源点的间隔值最短途径为0；V-S中各中各个顶点的间隔值为：只经过源点到达该顶点的当时最短个顶点的间隔值为：只经过源点到达该顶点的当时最短途径，即从源点到达该顶点的边长无边时，间隔值为途径，即从源点到达该顶点的边长无边时，间隔值为。当某点的间隔值不等于。当某点的间隔值不等于时，可以得到该点的途径时，可以得到该点的途径一条边。一条边。首先，从首先，从V-S中选择一个间隔值最小的顶点中选择一个间隔值最小的顶点v，将其参与，将其参与到到S中，扩展

23、集合中，扩展集合S。此时该点的间隔值就是最短途径长。此时该点的间隔值就是最短途径长度。度。然后，对集合然后，对集合V-S中剩余顶点的间隔值进展修正。方法是中剩余顶点的间隔值进展修正。方法是：假设：假设u是是V-S中的一个顶点，中的一个顶点，u点当前的间隔值为点当前的间隔值为len_u，而新参与，而新参与S的点的点m的最短途径的最短途径len_m加上边加上边 的的长度为长度为L，假设，假设Llen_u，那么，那么u点当前的间隔值修正为点当前的间隔值修正为：len_u=L。同时修正途径，即在。同时修正途径，即在m点的途径后面加上点的途径后面加上u点即可。点即可。最后，反复最后，反复2、3步，直到一

24、切顶点全部进入集步，直到一切顶点全部进入集合合S，即，即V=S为止。为止。 1. 初始化：S= 1，V-S= 2，3，4，5。各点的间隔值及途径为： 2. 从V-S中选择间隔值最小的顶点2，参与到S中。此时S= 1，2，V-S= 3，4，5。然后对V-S中各点的间隔值进展修正，修正后各点的间隔值及途径为： 3.再从V-S中选择间隔值最小的顶点4，参与到S中。此时S= 1，2，4， V-S= 3，5。修正V-S中的点的间隔值为： 4. 继续从V-S中选择间隔值最小的顶点3，参与到S中。此时S= 1，2， 3，4，V-S= 5。修正V-S中的点的间隔值为：5.最后从V-S中选择间隔值最小的顶点5，

25、参与到S中。此时S= 1，2， 3，4，5，V-S= ，算法终了。存前点方式存储构造 存储构造C言语描画：typedef struct int prenode; int pathlength;shortestpath;int flagn+1;shortestpath spn+1; 恣意两点间最短路经 Floyd算法的实现是经过矩阵迭代来完成的。有向图及其邻接矩阵 66 拓扑排序拓扑排序 拓扑排序是有向无环图拓扑排序是有向无环图directed acycline graph上的重要运算。拓扑排序的目的是将上的重要运算。拓扑排序的目的是将有向无环图中一切的顶点排成一个线性序列有向无环图中一切的顶点

26、排成一个线性序列，通常称为拓扑序列。，通常称为拓扑序列。 拓扑序列必需满足如下条件：对一个有向无拓扑序列必需满足如下条件：对一个有向无环图环图G=V，E，假设顶点，假设顶点u，vV，且，且u到到v有途径，那么在此线性序列中，顶点有途径，那么在此线性序列中，顶点u必必陈列在顶点陈列在顶点v之前。之前。 AOV网网 ：用顶点表示活动，顶点之间的有向：用顶点表示活动，顶点之间的有向边表示活动之间的先后关系，从而将实践问边表示活动之间的先后关系，从而将实践问题转化为一个有向图，称其为顶点活动网题转化为一个有向图，称其为顶点活动网Activity On Vertex network，简称，简称AOV网网

27、。 可以得到拓扑序列：C1，C3，C3，C4，C5，C6，C7，C8，C9，C10和C2，C6，C1，C5，C7，C10，C4，C3，C8，C9 拓扑排序的方法在有向图中选一个没有前驱的顶点且输出之从网中删除该顶点及一切出边反复上述两步，直至全部顶点均已输出；或者当网中不存在入度为0的顶点为止。一个AOV网的拓扑序列不是独一的AOV网求拓扑排序的过程 算法实现以邻接表作存储构造每次都需求查找入度为0的顶点并删除出边，在邻接表上删除出边很容易，而要查找入度为0的顶点需求遍历一切的单链表，较费事。为此，添加一个存放顶点入度的域id，先将每个顶点的入度求出后依次存放在该域中。反复上述操作直至栈空为止,拓扑排序终了。67 关键途径关键途径 关键途径那么是关键途径那么是AOE网网Activity On Edge network上的典型运算上的典型运算 在