《数据结构与算法》第七章图.ppt

1、第七章 图,7.1 图的定义 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径,71图的定义,一、有向图和无向图 顶点Vertex V:顶点的有穷非空集合 VR两个顶点之间的关系的集合 若VR 则表示从v到w有一条弧Arc v称作弧尾或初始点，Tail w称作弧头或终端点, Head,有向图,无向图,稀疏图 稠密图 网Network,子图,邻接点 相关联 顶点的度、入度、 出度,图中边/弧的数目与顶点度的关系,路径,路径的长度,连通图,回路或环Cycle 简单路径 简单回路,强连通图,完全图,有向完全图,由顶点的集合和弧的集合构成的图

2、称为有向图,G1=(V1,A1) V1=v1,v2,v3,v4 A1=,若VR必有VR 则用无序对(v,w)代替和称作边Edge 由顶点的集合和边的集合构成的图称作无向图,G2=(V2,E2) V2=v1,v2,v3,v4,v5 E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5),二、完全图 Completed Graph 完全图 有n*（n-1）/2条边的无向图 有向完全图 有n*（n-1）条弧的有向图 稀疏图 有很少条边或弧的图 稠密图 网Network 带权的图,三、子图Subgraph 若有两个图G =（V，E）,G1=（V1，E1）

3、如果V1 V , E1 E,则称G1为G的子图,子图,四、度 1.无向图G =（V，E） 若边（v，v1）E，则称顶点v和v1互为邻接点 边（v，v1）依附于顶点v和v1 或边（v，v1）与顶点v、v1相关联 顶点v的度是和v相关联的边的数目,记作TD（v） 2.有向图G =（V，A） 弧v，v1A， 则称v邻接到v1 或v1邻接自v 弧v，v1和顶点v、v1相关联 以顶点v为头的弧的条数称作v的入度,记作ID（v） 以顶点v为尾的弧的条数称作v的出度,记作OD（v） 顶点v的度TD（v）=ID（v）+OD（v）,图中边/弧的数目与顶点度的关系,(若图中有n个顶点，e条边/弧),五、路径 1.

4、无向图G=（V，E）中 从顶点v到v1的路径是一个顶点序列: v=Vi,0, Vi,1,Vi,m =v1 其中（Vi,j-1，Vi,j）E， 1jm,3.路径的长度是路径上边或弧的数目,2.有向图G=（V，A） 从顶点v到v1的路径是一个有向顶点序列: v=Vi,0, Vi,1,Vi,m=v1 其中Vi,j-1，Vi,jA， 1jm,4.第一个顶点与最后一个顶点相同的路径称为回路或环Cycle 5.序列中顶点不重复出现的路径称为简单路径 除第一个和最后一个顶点外，其余顶点不重复出现的回路称为简单回路,六、连通图 Connected Graph 1.无向图 v到v1有路径，称v和v1是连通的 若

5、图中任意两个顶点vi、vjV都是连通的 则称G是连通图,2.若一个无向图中有n个顶点和少于n-1条边 则该图是非连通图 若它有多于n-1条边，则一定有环,3.有向图 对于每一对vi、vjV,从vi到vj和vj到vi 都存在路径,则称 G为强连通图,七、图的ADT ADT Graph 数据对象V:V是具有相同特性的数据元素的集合，称为顶点。 数据关系R： R=VR VR=|v,wV且p(v,w), 表示从v到w的弧， 谓词P(v,w)定义了弧的意义或信息 基本操作P： CreateGraph( 初始条件:图G存在. 操作结果:销毁图G。,LocateVex(G,u); 初始条件：图G存在，u和G

6、中顶点有相同特征。 操作结果: 若G中存在顶点u，则返回该点在图中的位置,否则返回其它信息。,GetVex(G,v); 初始条件：图G存在，v是G中某个顶点。 操作结果: 返回v的值,PutVex( 初始条件：图G存在，v是G中某个顶点。 操作结果: 对v赋值 value。,FirstAdjVex(G,v); 初始条件：图G存在，v是G中某个顶点。 操作结果:返回v的第一个邻接顶点。 若顶点在G中没有邻接顶点，则返回“空”。,NextAdjVex(G,v,w); 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。 操作结果: 返回v的（相对于w的）下一个邻接顶点。 若w是v 的最后一个邻

7、接点则返回“空”。,InsertVex( 初始条件：图G存在，v和图中顶点有相同特征。 操作结果: 在图G中增添新顶点v。,DeleteVex( 初始条件：图G存在，v是G中某个顶点 操作结果：删除G中顶点v及其相关的弧。,InsertArc( 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在G中删除弧。若G是无向的，则还删除对称弧,DFSTraverse(G,v,Visit(); 初始条件：图G存在，v是G某个顶点，Visit是顶点的应用函数。 操作结果:从顶点v起深度优先遍历图G，并对每个顶点调用visit一次且 仅一次。一旦visit()失败，则操作失败。 BFSTraverse

8、(G,v,Visit(); 初始条件：图G存在，v是G某个顶点，visit是顶点的应用函数。 操作结果: 从顶点v起广度优先遍历图G， 并对每个顶点调用visit 一次且仅一次。 一旦visit()失败，则操作失败。 ADT Graph,7.2 图的存储结构,在图中，无法用数据元素在存储区的物理位置表示元素之间的关系。,一、数组表示法(邻接矩阵表示法) 用一个数组存储顶点的信息， 用另一个数组存储边或弧的信息-邻接矩阵,15,10,5,30,12,20,3,2,1,0,4,1.图的数组存储表示 / _ _ _ _ _ _图的数组（邻接矩阵）存储表示 _ _ _ _ _ _ _ #define

9、INFINITY INT_MAX / 最大值 #define MAX_VERTEX_NUM 20 /最大顶点个数 typedef enum DG,DN,UDG,UDNGraphKind; /有向图，有向网，无向图，无向网 typedef struct ArcCell VRType adj; /VRType是顶点关系类型.对无权图,用1或0 /表示相邻否；对带权图，则为权值类型。 InfoType *Info; /该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,typedef struct VertexType vexsMAX_

10、VERTEX_NUM; / 顶点向量 AdjMatrix arcs; / 邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧数 GraphKind kind; / 图的种类标志 MGraph;,Mgraph G1; G1.vexnum=4 G1. arcnum=4 G1.kind=DG,G1.arcs01.adj=1,G1.arcs,2图的构造方法 Status CreateGraph( MGraph / CreateGraph,Status CreateUDN(MGraph /adj,info,for (k=0; k的权值 if (IncInfo) Input(* G.

11、); / 若弧含有相关信息,则输入 G.arcsji =G.arcsij; / 置的对称弧 return OK; / CreateUDN,二、邻接表Adjacency List 方法：对每个顶点建立一个单向链表 链接与vi有边相连的顶点（无向图） 或从vi出发到达的顶点（有向图）,指向该点出发到达的第一条弧,每个顶点对应一个头结点,每条边/弧对应一个结点,无向图,边结点,有向图,/- - - - - - - 图的邻接表存储表示 - - - - - - - #define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex

12、; / 该弧所指向的顶点的位置 struct ArcNode * nextarc; / 指向下一条弧的指针 InfoType * info; / 该弧相关信息的指针 ArcNode ;,typedef struct VNode VertexType data; / 顶点信息 ArcNode * firstarc; / 指向第一条依附顶点的弧的指针 VNode, AdjListMAX_VERTEX_NUM ;,typedef struct AdjList vertices; int vexnum, arcnum; / 图的当前顶点数和弧数 int kind; / 图的种类标志 ALGraph;,

13、# define MAX_VERTEX_NUM 20 typedef struct ArcBox int tailvex, headvex ; / 该弧的尾和头顶点的位置 struct ArcBox *hlink, *tlink; /分别为弧头相同和弧尾相同的弧的链域 Info type *info; / 该弧相关信息的指针 ArcBox;,typedef struct VexNode VertexType data; ArcBox * firstin, * firstout; /分别指向该顶点第一条入弧和出弧 VexNode ; typedef struct VexNode xlist MA

14、X_VERTEX_NUM ; / 表头向量 int vexnum, arcnum; / 有向图的当前顶点数和弧数 OLGraph ;,Status CreateDG(OLGraph / 初始化指针 ,for(k=0; kinfo); /若弧含有相关信息，则输入 / CreateDG,四、邻接多重表 Adjancency Multilist 顶点和边分别用一个结点表示 边：,该边是否搜索过,顶点i在图中的位置(编号),下一条与i有关的边,有关边的信息,# define MAX_VERTEX_NUM 20 typedef enum unvisited, visitedVisitIf ; typed

15、ef struct EBox VisitIf mark; / 访问标记 int ivex, jvex; / 该边依附的两个顶点的位置0 struct EBox * ilink, * jlink; /分别指向依附这两个顶点的下一条边 InfoType * info; / 该边信息指针 EBox; typedef struct VexBox VertexType data; EBox * firstedge ; / 指向第一条依附该顶点的边 VexBox;,typedef struct VexBox adjmulist MAX_VERTEX_NUM ; int vexnum, edgenum; /

16、 无向图的当前顶点数和边数 AMLGraph ;,73图的遍历Traversing Graph,图的遍历： 从图中某个顶点出发访问遍图中每个顶点， 且图中每个顶点仅被访问一次。 遍历过程中每个顶点可能被访问多次， 因此，每个顶点被访问后需作一个标记 一般用一个数组标记某个结点是否被访问 遍历方法：深度优先搜索、广度优先搜索,一、深度优先收索Depth-First-Search(DFS) 方法： 从图中某个顶点出发（设为v1），访问v1， 从v1出发,选择一个未被访问的邻接点vk,访问vk， 从vk出发，选择一个未被访问的邻接点, 若vk的所有邻接顶点都被访问过了， 回到vk-1,再选择的一个未

17、被访问的邻接点, 若图中仍有未被访问的顶点， 从中选择一个作为起点，重复上述过程 直到所有顶点均被访问过为止。,从v1出发,选择一个未被访问的邻接点vk,访问vk， 从vk出发，选择一个未被访问的邻接点, 若vk的所有邻接顶点都被访问过了， 回到vk-1,再选择的一个未被访问的邻接点, 若图中仍有未被访问的顶点， 从中选择一个作为起点，重复上述过程 直到所有顶点均被访问过为止。,Boolean visitedMAX; / 访问标志数组 Status (* VisitFunc)(int v); / 函数指针变量 void DFSTraverse(Graph G, Status(* Visit)(

18、int v) / 对图G作深度优先遍历 VisitFunc = Visit; /使用全局变量VisitFunc，使DFS不必设函数指针参数 for(v=0; vG.vexnum; +v) visitedv = FALSE ; / 访问标志数组初始化 for(v=0; vG.vexnum; +v ) if(!visitedv) DFS (G,v ); /对尚未访问的顶点调用DFS ,/从第v个顶点出发递归地深度优先遍历图G void DFS(Graph G, int v) visitedv=TRUE; VistFunc(v); /访问第v个顶点 for(w=FirstAdjVex(G,v);w0

19、; w=NextAdjVex(G,v,w) if(!visitedw) DFS(G,w); /对v的尚未访问的邻接顶点w递归调用DFS printf(v); /起什么作用 ,1,2,3,4,5,6,7,8,9,搜索,回退,二、广度优先收索Breadth-First-Search(BFS) 方法： 从图中某个顶点出发（设为vi），访问vi， 从vi出发，依次访问vi的所有未被访问的邻接点， 再从这些邻接点出发， 依次访问它们的所有未被访问的邻接点, 若图中仍有未被访问的顶点， 从中选择一个作为起点，重复上述过程 直到所有顶点均被访问过为止。,void BFSTraverse(Graph G,St

20、atus(* Visit)(int v) / 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。 for(v=0; v0;w=NextAdjVex(G,u,w) if(!visitedw) visitedw = TRUE; Visit(w); EnQueue(Q,w); / u的尚未访问的邻接顶点w入队列Q /while / if / BFSTraverse,搜索,1,2,3,4,5,6,7,8,9,74图的连通性问题,一、无向图的连通分量和生成树 1.连通分量 无向图的极大连通子图。即:子图中不能再增加一个顶点,已有顶点的边均包含在内。 无向图的连通分量的产生-多次调用D

21、FS 2.生成树 一个连通图的生成树是一个极小连通子图,且含有图中全部顶点,无向图,连通分量,连通图,生成树,3.无向图的生成树 对一个连通图G，从图中任意一个顶点出发遍历图时，把E分为E1和E2，E1为遍历过程中经过的边的集合，E2为剩余边的集合，则E1与V构成G的极小连通图，即连通图的一棵生成树 若遍历为DFS，则称为深度优先生成树 若遍历为BFS，则称为广度优先生成树,对于非连通图，每个连通分量中的顶点集合,加上遍历时经过的边，构成了非连通图的生成森林。,生成森林,4.无向非连通图的深度优先生成森林 void DFSForest(Graph G,CSTree /建立以p为根的生成树 /D

22、FSForest,void DFSTree(Graph G, int v, CSTree /从第w个顶点出发深度优先遍历图G,建立子生成树q / if / DFSTree,二、最小生成树Mininum Cost Spanning Tree 问题： 设有n个城市，两个城市之间都可以有一条路线，如何从最多n(n-1)/2条边中选择代价和最小的n-1条边(要包含所有顶点),就是连通图的最小代价生成树问题，简称最小生成树。,1.普里姆算法Prim 设N=（V，E）为连通网 用TE表示N上最小生成树边的集合 (1)从V中选一顶点u0加入U，TE= (2)对所有uU，vV-U，（u，v）E,找一条代价最小

23、的边（u0，v0）加入TE,并把v0加入U (3)重复(2)，直到U=V为止,则（V，TE）为N的最小生成树,U,V-U,v4,v6,v1,v2,v3,v5,1,5,5,5,6,6,6,3,4,2,2MST性质(Prime算法正确性证明） 设N=(V,E)是一个连通图, U是V的一个非空子集 若(u,v)是一个具有最小代价的边,uU，vV-U 则必存在一棵包含边(u ,v)的最小生成树,u,v,u,v,U,V-U,证明： 假设网N的任何一棵最小生成树都不包含(u ,v) 设T是N上的一棵最小生成树，把(u ,v)加入到T中 则T中必存在一条包含(u ,v)的回路 同时,T中必存在另一条边(u,

24、v)， 其中uU vV-U 并且u和u ,v和v之间均存在路径相通 删去边(u,v)，则可削去回路， 得到另一棵生成树T 显然,T的代价不高于T,且包含边(u ,v),矛盾。,设N=（V，E）为连通网 用TE表示N上最小生成树边的集合 (1)从V中选一顶点u0加入U，TE= (2)对所有uU，vV-U，（u，v）E,找一条代价最小的边（u0，v0）加入TE,并把v0加入U (3)重复(2),直到U=V为止,则（V,TE）为N的最小生成树,图-邻接矩阵 最小的边（u0，v0）（ u0U，v0V-U）用矩阵closedge表示,struct VertexType adjvex; /最短的边对应u中

25、的顶点 VRType lowcost;/记录u中顶点到顶点j的最短的边 closedgeMAX_VERTEX_NUM;,void MiniSpanTree_PRIM(MGraph G,VertexType u) k = LocateVex(G, u ); for(j=0;jG.vexnum; +j ) / 辅助数组初始化 if(j!=k) closedgej=u,G.arcskj.adj; /adjvex,lowcost closedgek.lowcost = 0; / 初始，U = u,for(i=1; iG.vexnum;+i) / 选择其余G.vexnum-1个顶点 k =minimum

26、(closedge); /求出T的下一个结点:第k顶点 printf(closedgek.adjvex,G.vexsk); /输出生成树的边 closedgek.lowcost = 0; /第k顶点并入U集 for (j=0; jG.vexnum; +j) if(G.arcskj.adjclosedgej.lowcost) closedgej=G.vexsk,G.arcskj.adj; / MiniSpanTree,3.克鲁斯卡尔算法 设连通图N=（V，E） (1)构造非连通图T=(V,),图中每个顶点自成一个连通分量 (2)在E中选择代价最小的边（u，v），并删去该边。若(u,v)落在T中不

27、同的连通分量上,则将此边加入T中 (3)重复(2），直到T中只有一个连通分量为止,2,4,5,3,6.5有向无环图及其应用,一、DAG图 -Directed Acycline Graph 一个无环的有向图称为有向无环图,二、拓扑排序 Topological Sort 1AOV网 Activity On Vertex Network 用顶点表示活动， 用弧表示活动之间的优先关系的有向图 称为顶点表示活动的网，简称AOV网。 在网中,若顶点i到顶点j有一条路径,则i为前驱, j为后继。若A，则vi为vj的直接前驱，vj为vi直接后继,在AOV网中不能出现环，判定网中是否出现环的办法是拓扑排序。若所

28、有的顶点都在拓扑有序序列中，则AOV网中无环，否则有环。,C语言程序设计,数据结构与算法,面向对象程序设计,计算机网络原理,信息科学导论,电路原理,大学物理,数字逻辑电路实验,组成原理实验,操作系统,汇编语言程序设计,高等数学1,离散数学,数据库原理,线性代数,基础物理实验B,高等数学2,高等数学3,C程序设计实验,数据结构实验,电路原理实验,概率与数理统计,数字逻辑电路,计算机组成原理,网络原理实验,操作系统实验,面向对象实验,2拓扑次序 设AOV网中有n个顶点V1，V2，Vn， 将顶点排成这样一个线性次序：Vi1，Vi2，Vin， 其中i1，i2，in是1到n的一个排列 且若V ij，V

29、ikA，则jk,对AOV网给出拓扑次序的过程称为拓扑排序,3拓扑排序算法 (1)在网中选一个没有前驱的顶点且输出它 (2)从图中删去该顶点及所有以它为尾的弧 (3)重复(1)(2)直到所有顶点被输出 或图中不存在无前驱的顶点为止,。采用邻接表作存储结构 。用一个数组indegree存放顶点的入度 。用一个栈存放入度为0的顶点,Status TopologicalSort( ALGraph G) /有向图G采用邻接表存储结构。 /若G无回路,则输出G的顶点的一个拓扑序列并返回OK, /否则ERROR FindInDegree(G,indegree); /对各顶点求入度indegree InitS

30、tack(S); / 建零入度顶点栈S for(i=0; iG.vexnum; +i ) if(!indegreei) Push(S, i); / 入度为0者进栈 count = 0; / 对输出顶点计数,while(!StackEmpty(S) Pop(S,i); printf(i,G.verticesi.data); +count; / 输出i号顶点并计数 for(p=G.verticesi.firstarc; p; p=p-nextarc) k = p-adjvex; /对i 号顶点的每个邻接的入度减1 if(!(- -indegreek)Push(S, k); /若入度减为0，则入栈

31、/ for DestroyStack(S); if(countG.vexnum) return ERROR; /该有向图有回路 else return OK; / TopologicalSort,。还可以利用深度优先遍历过程进行拓扑排序，按退出DFS的逆序为拓扑次序,1,2,3,4,5,6,拓扑次序为：v6、v1、v4、v3、v5、v2,4.关键路径 AOE网Activity On Edge 顶点-事件 边-活动 权-活动持续的时间 用AOE网估计工程的完工时间,Vi表示在此之前的活动已完成，在此之后的活动可以开始,1,2,3,4,5,买面粉3,买鸡蛋3,买白菜4,买熟食6,6,7,剁馅5,切

32、2,和面2,煮鸡蛋1,包饺子4,最短要多久才能包好饺子,开始聚餐?,在一般情况下,AOE网中只有一个入度为0的顶点,称为源点 只有一个出度为0的顶点，称为汇（聚）点 ？完成整个工程至少需要多少时间 -从源点到汇点的最长路径 ？哪些活动是影响工程进度的关键,路径长度最长的路径叫做关键路径 Critical Path 从源点到Vi的最长路径叫做事件的最早发生时间,也就是所有以Vi为尾的弧所表示活动的最早开始时间,令e(i)表示ai的最早开始时间 l(i)表示ai的最迟开始时间 l(i)-e(i)为时间余量 关键路径上的所有活动有：l(i)=e(i) 把所有e(i)=l(i)的活动叫做关键活动。,设

33、ai由弧表示 ve(j)表示事件j的最早发生时间 vl(j)表示事件j的最迟发生时间 ai的持续时间为dut() 则：e(i)=ve(j) l(i)=vl(k)-dut(),最早开始时间:前驱活动都按期完成情况下的开始时间 最迟开始时间:保证所有活动都能按期完成情况下最晚开始时间 关键路径上的所有活动最早=最迟,计算的方法： （1）ve(0)=0 （2）按拓扑顺序计算：,其中T是所有以第j个顶点为头的弧的集合,（3）vl(n-1)=ve(n-1) （4）按逆拓扑顺序计算：,其中S是所有以第i个顶点为尾的弧的集合,（5）根据各顶点的ve和vl的值 计算每条弧s的e(s)和l(s),ve(3)=5

34、,ve(4)=7,ve(7)=14,ve(8)=18,vl(8)=18,vl(7)=14 vl(6)=16,vl(4)=7,ve(0)=0,vl(1)=6 vl(2)=6,vl(0)=0,ve(5)=7,ve(6)=16,vl(5)=10,vl(3)=8,ve(2)=4 ve(1)=6,Status TopologicalOrder(ALGraph G, Stack / 初始化,while (! StackEmpty(S) Pop(S, j); Push(T,j); +count; /j号顶点入T栈并计数 for(p=G.verticesj.firstarc;p;p=p-nextarc) k

35、= p-adjvex; / 对j号顶点的每个邻接点的入度减1 if(-indegreek=0)Push(S, k); /若入度减为0，则入栈 if(vej+*(p-info)vek)vek=vej+*(p-info); / *(p-info)= dut() / while DestroyStack(S); if(countG.vexnum) return ERROR; /该有向网有回路 else return OK; / TopologicalOrder,Status CriticalPath(ALGraph G) /G为有向网，输出G的各项关键活动 if(!TopologicalOrder(

36、G,T) return ERROR; vl0.G.vexnum-1=veG.vexnum-1; /初始化顶点事件的最迟发生时间 while (! StackEmpty(T) /按拓扑逆序求各顶点的v1值 for(Pop(T,j),p=G.verticesj.firstarc; p; p=p-nextarc) k=p-adjvex; dut = * (p-info); / dut if(vlk-dutv1j) vlj = vlk-dut; / for,for(j=0;jnextarc) k = p-adjvex; dut = * (p-info) ; ee=vej; el=vlk-dut; ta

37、g=(ee=e1)? * : ; printf ( j,k, dut, ee, el, tag); / 输出关键活动 / CriticalPath,76最短路径 用顶点表示城市， 用边表示城市之间的交通状况 用边上的权表示城市之间的耗费（距离、时间、各种费用等） 一、从一点到另一点，经过的结点最少 二、从某个源点到其余各个顶点的最短路径 给定带权的有向图G和源点v， 求从v到G中其余各点的最短路径 方法：按路径长度递增序产生最短路径 -迪杰斯特拉Dijksta方法,v0,v5,60,v1,v2,v3,v4,100,30,10,10,50,5,20,v0,v5,v1,v2,v3,v4,存储结构 用带权的邻接矩阵arcs表示带权有向图 arcsij= A 上的权值 A,算法 (1)设S为已找到从v出发的最短路径的终点集合, 初值S= Di表示从v到Vi的最短路径的长度 若A,Di为从v到Vi上的权,否则为 即：Di=arcsLo