《数据结构II5-第7章.ppt》由会员分享，可在线阅读，更多相关《数据结构II5-第7章.ppt（65页珍藏版）》请在三一办公上搜索。
1、,第7章 图 7.1 图的定义和术语 图(Graph)是一种数据结构，形式定义 Graph=(V,R)其中：V=x|xdataobject R=VR VR=|p(x,y)(x,y V)p(x,y)表示从x到y的一条通路,图的抽象数据类型定义：ADT Graph 数据对象V:V是具有相同特性的数据元素的集合，称为顶 点集。数据关系R：R=VR VR=|v,wV且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息 基本操作P：GreateGraph(ADT Graph,例如：G1=(v1,A1)其中：v1=v1,v2,v3,v4,A1=,例如：G2=(v2,E2)其中：v2=v1
2、,v2,v3,v4,v5 E2=(v1,v2),(v1,v4),(v2,v3)(v2,v5),(v3,v4),(v3,v5),设图中顶点数为n，边或弧数为e，则：,对于无向图，e的取值范围为0n(n-1)/2,具有n(n-1)/2条边的无向图称为完全图,对于有向图，e的取值范围为0n(n-1),具有n(n-1)条边的有向图称为有向完全图,和图中边相关的数叫作权（weigth）,带权的图称为网,顶点的度是和该顶点相关联的边的数目。记作TD(v),以顶点v为头的弧的数目称为v的入度。记作ID(v),以顶点v为尾的弧的数目称为v的出度。记作OD(v),顶点v的度 TD(v)=ID(v)+OD(v),
3、邻接点：对于无向图G=(V,E)，如果边(v,v)E,则称顶 点v和v互为邻接点,路径：路径是顶点的序列V=Vi0,Vi1,Vin，满足(Vij-1,Vij)E 或 E,(1jn)路径长度：沿路径边的数目或沿路径各边权值之和回路：第一个顶点和最后一个顶点相同的路径简单路径：序列中顶点不重复出现的路径简单回路：除了第一个顶点和最后一个顶点外，其余顶点不 重复出现的回路连通：从顶点V到顶点W有一条路径，则说V和W是连通的连通图：无向图中任意两个顶点都是连通的连通分量：无向图中的极大连通子图强连通图：有向图中，如果对每一对Vi,VjV,ViVj,从Vi到 Vj 和从Vj到 Vi都存在路径，则称G是强
4、连通图强连通分量：有向图中的极大强连通子图,有向完全图：具有n(n-1)条边的有向图无向完备图：具有n(n-1)/2 条边的无向图权：与图的边或弧相关的数网：带权的图,7.2 图的存储结构多重链表,实际中不适用,数组表示法（邻接矩阵）设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵,图的数组（邻接矩阵）存储表示#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20typedef enum DG,DN,UDG,UDN GraphKind;typedef struct ArcCell VRType adj;InfoType*in
5、fo;ArcCell,djMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexs MAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;GraphKind kind;MGraph;,特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n无向图中顶点Vi的度TD(Vi)是邻接矩阵中第i行元素之和有向图中，顶点Vi的出度是邻接矩阵中第i行元素之和顶点Vi的入度是邻接矩阵中第i列元素之和易于实现
6、基本操作,采用数组（邻接矩阵）表示法，构造图GStatus CreateGraph(MGraph,采用数组（邻接矩阵）表示法，构造无向网GStatus CreateUDN(MGraph return OK,邻接表表示,图的邻接表存储表示#define MAX_VERTEX_NUM 20typedef struct ArcNode int adjvex;struct ArcNode*nextarc;InfoType*info;ArcNode;typedef struct Vnode VertexType data;ArcNode*firstarc;Vnode,AdjList MAX_VERTEX
7、_NUM;typedef struct AdjList Vertices;int vexnum,arcnum;int kind;ALGraph;,特点若无向图中有n个顶点、e条边，则需n个头结点和2e个表结点无向图中顶点Vi的度为第i个单链表中的结点数有向图中顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表,十字链表-有向图的另一种存储结构,有向图的十字链表存储表示#define MAX_VERTEX_NUM 20typedef struct ArcBox int tailvex,headvex;
8、struct ArcBox*hlink,*tlink;InfoType*info;ArcBox;typedef struct VexNode VertexType data;ArcBox*firstin,*firstout;VexNode;typedef struct VexNode xlist MAX_VERTEX_NUM;int vexnum,arcnum;OLGraph;,采用十字链表存储结构，构造有向图Status CreateDG(OLGraph,无向图的邻接多重表存储表示#define MAX_VERTEX_NUM 20typedef emnu unvisited,visited
9、VisitIf;typedef struct EBox VisitIfmark;int ivex,jvex;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;AMLGraph;,邻接多重表-无向图的另一种存储结构,7.3 图的遍历,图的遍历：从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。,在线性结构
10、中，元素之间的关系为前驱和后继；在树结构中，结点之间的关系为双亲和孩子；在图结构中，顶点之间的关系为邻接。,7.3 图的遍历 不同结构中逻辑关系的对比,一、深度优先搜索(Depth First Search)方法：从图的某一顶点V出发，访问此顶点；然后依次从V的未被访问的邻接点出发，深度优先搜索图，直至图中所有和V有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。,深度优先搜索序列：,V1,V2,V3,V1,V4,V5,V6,V7,V2,V8,V7,V3,V4,V5,V3,V6,V2,V8,v1,v2,v4,
11、v8,v5,v3,v6,v7,遍历操作中要解决的关键问题：,“从图的某一顶点V出发”，如何选取出发顶点。,解决方案：按存储结构排列顺序的第一个。,“依次从V的未被访问的邻接点出发”中“依次”,解决方案：按基本操作，先找第一邻接点，再找下一个,循环查找各邻接点。,“未被访问的”邻接点,解决方案：设访问标志数组visited,非连通图,解决方案：从任意一个未被访问的结点出发调用算法,算法7.4 7.5 深度优先算法Boolean visited MAX;Status(*VisitFunc)(int v);void DFSTraverse(Graph G,Status(*Visit)(int v)V
12、isitFunc=Visit;for(v=0;v G.vexnum;+v)visited v=FALSE;for(v=0;v G.vexnum;+v)if(!visited v)DFS(G,v);void DFS(Graph G,int v)visited v=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w)if(!visited w)DFS(G,w);,问题：判断给定图是否是连通图？多少个连通分量,深度遍历：V1,V2,V4,V8,V5,V3,V6,V7,void DFS(Graph G,int v)visited
13、v=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w)if(!visited w)DFS(G,w);,邻接矩阵存储结构void DFS(MGraph G,int v)visited v=TRUE;VisitFunc(v);for(j=0;jG.vexnum;j+)if(G.arcsvj.adj=1,邻接表存储结构void DFS(ALGraph G,int v)visited v=TRUE;VisitFunc(v);p=G.verticesv.firstarc;while(p)if(!visitedp-adjvex)DF
14、S(G,p-adjvex);p=p-nextarc;,时间复杂度：O(n2),时间复杂度：O(n+e),二、广度优先搜索(Breadth First Search)方法：从图的某一顶点V出发，访问了V之后，依次访问V的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先搜索图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问为止。,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8,void BFSTraverse(Graph G,Status(*visit)(int v)for(
15、v=0;v G.vexnum;+v)visited v=FALSE;InitQueue(Q);for(v=0;v G.vexnum;+v)if(!visited v)visited v=TRUE;visit(v);EnQueue(Q,v);while(!QueueEmpty(Q)DeQueue(Q,u);for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w)if(!visited w)visited w=TRUE;visit(w);EnQueue(Q,w)/if/while/if,时间复杂度：邻接矩阵存储：O(n2)邻接表存储：O(n+e),问题：二叉树按层次
16、遍历,问题：迷宫问题,7.4 图的连通性问题一、无向图的连通分量和生成树,对无向非连同图进行深度优先遍历,三次调用得到的访问序列为：,ALMJBFC,DE,GKHI,A,B,C,D,E,F,G,H,I,J,K,L,M,生成树：所有顶点均由边连接在一起，但不存在回路的图。深度优先生成树与广度优先生成树生成森林：非连通图每个连通分量的生成树一起组成非连通图的生成森林。说明一个图可以有许多棵不同的生成树所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同生成树是图的极小连通子图一个有n个顶点的连通图的生成树有n-1条边生成树中任意两个顶点间的路径是唯一的在生成树中再加一条边必然形成回路含n
17、个顶点n-1条边的图不一定是生成树,建立非连通图G的深度优先生成森林void DFSForest(Graph G,CSTree,从第v个顶点出发深度优先遍历图G，建立以T为根的生成树void DFSTree(Graph G,int v,CSTree,二、最小生成树,问题提出：要在n个城市间建立通信联络网，顶点表示城市，边上的权值表示城市间建立通信线路所需花费代价，现希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小最小代价生成树。,问题分析：,9,9,18,8,6,26,13,12,n个城市间，最多有n(n-1)/2条线路,n个城市间建立通信网，只需n-1条线路,
18、问题转化为：如何在可能的线路中选择n-1条，能把所有城市（顶点）均连起来，且总耗费(各边权值之和)最小。,构造一个最小生成树,1,2,3,4,5,性质：假设N=(V,E)是一个连通网，U是顶点集V的一个非空子集。若（u,v）是一条具有最小权值（代价）的边，其中uU,vV-U，则必存在一棵包含边(u,v)的最小生成树。,普里姆(Prim)算法算法思想：设N=(V,E)是连通网，TE是N上最小生成树中边的集合初始令U=u0,(u0V),TE=在所有uU,vV-U的边(u,v)E中，找一条代价最小的边(u0,v0)将(u0,v0)并入集合TE，同时v0并入U重复上述操作直至U=V为止，则T=(V,T
19、E)为N的最小生成树,6,5,1,3,5,6,6,4,2,5,1,2,3,4,5,6,1,2,3,4,5,6,Struct VertexType adjvex;VRType lowcost;closedgeMAX_VERTEX_NUM;,0,1,2,3,4,5,void MiniSpanTree_PRIM(MGraph G,VertexType u)k=LocateVex(G,u);for(j=0;j G.vexnum;+j)if(j!=k)closedge j=u,G.arcs k j.adj;closedge k.lowcost=0;for(i=1;i G.vexnum;+i)k=mini
20、mum(closedge);printf(closedge k.adjvex,G.vexs k);closedge k.lowcost=0 for(j=0;j G.vexnum;+j)if(G.arcs k j.adj closedge j.lowcost)closedgej=G.vexsk,G.arcskj.adj;,克鲁斯卡尔(Kruskal)算法算法思想：设连通网N=(V,E)，令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V,)，每个顶点自成一个连通分量在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边
21、依此类推，直至T中所有顶点都在同一连通分量上为止。,1,2,3,4,5,6,7.5 有向无环图及其应用,有向无环图（Directed Acycline Graph）一个无环的有向图,简称DAG图,DAG图,有向树,有向图,用有向无环图描述含有公共子式的表达式,例(a+b)*(b*(c+d)+(c+d)*e)*(c+d)*e),一、拓扑排序,拓扑排序（Topological Sort）:由某个集合上的一个偏序得到该集合上的一个全序，这个操作称为拓扑排序。,若集合X上的关系R是自反的，反对称的和传递的，则称R是集合X上的偏序关系。,设R是集合X上的偏序关系，如果对每个小x,yX 必有xRy或yRx
22、，则称R是集合X上的全序关系。,学生选修课程问题顶点表示课程有向弧表示先决条件，若课程i是课程j的先决条件，则图中有弧学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业拓扑排序,C1,C2,C3,C4,C5,C7,C9,C10,C11,C6,C12,C8,C9,C10,C11,C6,C1,C12,C4,C2,C3,C5,C7,C8,一个AOV网的拓扑序列不是唯一的,顶点表示活动，弧表示优先关系的有向图称为顶点表示活动的网（Activity On Vertex Network）简称AOV网,拓扑排序的方法1）在有向图中选一个没有前驱的顶点且输出之2）从图中删除该顶点和所有以它为尾的弧重复
23、上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止,C9,C1,C3,C2,C4,C5,C7,C6,C8,C12,C11,C10,拓扑排序算法：,1）扫描顶点表，求各顶点入度indegree0.vernum-1,2）初始化栈，入度为0的顶点入栈，计数count=0;,3）当栈不空时重复 1、取栈顶顶点，并输出，计数count+;2、取该顶点的所有邻接点将其入度减1，若减1后入度为0，则该顶点入栈。,4）当栈空时，若输出的顶点数count小于图的顶点数，则图有回路，否则正常,Status TopologicalSort(ALGraph G)FindInDegree(G,indegr
24、ee);/求各顶点的入度indegree0.vernum-1 InitStack(S);for(i=0;i nextarc)k=p-adjvex;if(!(-indegree k)Push(S,k);if(count G.vexnum)return ERROR;else return OK;,时间复杂度：O(n+e),二、关键路径 问题提出：,把工程计划表示为有向图，用顶点表示事件，弧表示活动；权表示活动持续的时间。,例 设一个工程有11项活动，9个事件事件 V1表示整个工程开始事件V9表示整个工程结束问题：（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？,AOE网(A
25、ctivity On Edge)边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。路径长度路径上各活动持续时间之和关键路径路径长度最长的路径Ve(j)表示事件Vj的最早发生时间Vl(j)表示事件Vj的最迟发生时间e(i)表示活动ai的最早开始时间l(i)表示活动ai的最迟开始时间l(i)-e(i)表示完成活动ai的时间余量关键活动关键路径上的活动。,0,6,4,5,7,7,14,16,18,18,14,16,7,10,8,6,6,0,5,11,求ve(j)和vl(j)需分两步进行：,1）从ve(0)=0开始向前递推：,ve(j)=Maxve(i)
26、+dut()i T j=1,2,n-1 其中：T为所有以j为头的弧的集合,算法实现1)从源点V1出发，令ve0=0,按拓扑序列求各顶点的最早开始时间vei2）从汇点Vn出发，令vln-1=ven-1,按逆拓扑序列求其余各顶点的最迟发生时间vli3）根据各顶点的Ve和Vl值，计算每条弧的最早开始时间ei和最迟开始时间li,找出ei=li的关键活动,Status TopologicalOrder(ALGraph G,Stack,Status CriticalPath(ALGraph G)if(!TopologicalOrder(G,T)return ERROR;vl 0.G.vexnum 1=ve
27、 G.vexnum 1;while(!StackEmpty(T)for(Pop(T,j),p=G.verticesj.firstarc;p;p=p-nextarc)k=p-adjvex;dut=*(p-info);if(vl k dut nextarc)k=p-adjvex;dut=*(p-info);ee=ve j;el=vl k dut;tag=(ee=el)?*:;printf(j,k,dut,ee,el,tag);,时间复杂度：O(n+e),7.6 最短路径,问题提出,图中：顶点：表示城市边：表示城市间的交通联系权：表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿
28、图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径最短路径,用带权的有向图表示一个交通运输网,一、从某个源点到其余各顶点的最短路径,迪杰斯特拉(Dijkstra)算法基本思想把图中所有顶点分成两组，第一组包含已确定最短路径的顶点，第二组包含尚未确定最短路径的顶点，按最短路径递增的顺序，逐个把第二组的顶点加到第一组中去，直至从V0出发可以达到的所有顶点都包含到第一组中。,第一组,第二组,v0,v1,v2,v3,v4,v5,v1=,v2=10,v3=,v4=30,v5=100,v2=10,v3=60(v2),v4=30,v5=90(v4),v3=50(v4),v5=60(v4 v3),
29、v5=60(v4 v3),v3=50(v4),求最短路径步骤初始时令 S=V0,T=其余顶点，T中顶点对应的距离值若存在，为弧上的权值若不存在，为从T中选取一个其距离值为最小的顶点W，加入S对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值重复上述步骤，直到S中包含所有顶点，即S=V为止,void DIJ(Mgraph G,int v0,PathMatrix,时间复杂度：O(n2),二、每一对顶点之间的最短路径方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次，其时间复杂度为：O(n),方法二：弗洛伊德(Floyd)算法,算法基本
30、思想：递推地产生一个矩阵序列：D(-1),D(0),D(n-1)其中：D(-1)=arcs;D(-1)ij等于从顶点vi到vj中间顶点序号不大于-1（即不经过任何中间顶点）的最短路径长度。D(0)ij等于从顶点vi到vj中间顶点序号不大于0的最短路径长度。即在vi，vj间考虑v0顶点，也就是判别（vi,vj）和（vi,v0,vj）(若存在)的最短者。D(1)ij等于从顶点vi到vj中间顶点序号不大于1的最短路径长度。D(n-1)ij等于从顶点vi到vj中间顶点序号不大于n-1的最短路径长度，即为所求从vi到vj的最短路径长度。,假设已求得矩阵 D(k-1)，求D(k)从顶点vi到vj中间顶点序
31、号不大于k的最短路径有两种情况：1）不经vk，则D(k)ij=D(k-1)ij 没有通路或有通路但经vk长度值较大 2）经vk，则 D(k)ij D(k-1)ij 若不小于，则属1）情况而路径D(k)ij为vi经vk到 vj的中间顶点序号不大于k的最段路径由两段组成；一段是从vi到 vk中间顶点序号不大于k-1的最段路径，一段是从vk到 vj中间顶点序号不大于k-1的最段路径。即：D(k)ij=D(k-1)ik+D(k-1)kj 条件：D(k)ij D(k-1)ij 即：D(k-1)ik+D(k-1)kj D(k-1)ij 因此：D(k)ij=min(D(k-1)ij,D(k-1)ik+D(k-1)kj)0 k n-1,举例：,void FLOYD(MGraph G,PathMatrix,
