数据结构图7.ppt

1、第七章 图,第一节 图的基本概念,图的定义： Graph=(V,E)， V为顶点集; E 为边集。 若 E 为有向边，称为有向图； 若 E 为无向边，称为无向图。 边一般由顶点对表示：; 若 为有向边,则称 vi 为尾, vj 为头. 有向边也可以表示为: vi vj,2,例如:,V=1,2,3,4 E=, ,无向图中, = ,无向完全图: 如果在无向图G中,任何两顶点都有一条边相连,则称此图 为无向完全图. n 个结点的无向完全图,边的数目为: n(n-1)/2,3,有向完全图: 如果在有向图G中,任何两顶点都有两条方向相反的边相 连, 则称此图为有向完全图. n 个结点的有向完全图,边的数

2、目为: n(n-1) 子图: 设有两个子图,G=(V,E),G=(V,E); 若V V,且 E E,则称G为G的子图。 网 ： 若 G 中的每一条边都有权值，称该图为网。 权值可以是距离，时间，价格等。,4,路径: 图中从顶点V到顶点V的路径是顶点序列: (V,Vi1,Vi2,.Vik,V) 且满足 , E 路径上所含边的数目称为路径长度. 回路: 第一个顶点和最后一个顶点相同的路径称为回路或环. 简单路径: 顶点 序列中,顶点不重复出现的路径称为简单路径. 简单回路: 除第一个和最后一个顶点外,其它顶点不重复出现的 回路称为简单回路.,5,连通图: 无向图中,任意两点 Vi,Vj 都有路径相

3、连,称该无向图 为连通图. 连通分量: 无向图中极大连通子图. 强连通图: 有向图中,若每一对顶点,从 Vi 到 Vj 和 Vj 到 Vi 都有路径相连,则称该图为强连通图.,例如:,非强连通 强连通,6,第二节 图的基本操作,Create_G( /有向无向图网 typedef struct / 图结构 Vextype vexsMax_V_num; / 顶点数组 Arctype arcsMax_V_num Max_V_num; /边矩阵 /0,1或权值wij int vexnum,arcnum; /顶点数,边数 Graphkind kind; /图种类 graph,若 G=(V,E) 为网,则

4、邻接矩阵可以表示为:,9,例如:,10,Status createUDN(Graph ,11,二 邻接表表示法 每个顶点用一个链表表示,头 结点:,a b c d,data firstarc,边 结点:,vjpos nexttarc,0123,vexs,12,#define Max_V_num 20 /最大顶点数 typedef struct Arcnode /边结点类型 int vjpos; /vj的位置 struct Arcnode *nextarc; Arcnode; typedef struct Vnode /顶点结点类型 vextype data; Arcnode *firsttar

5、c; Vnode,AdjlistMax_V_num ; typedef struct Adjlist vexs; int vexnum,arcnum; Graphkind kind; graph,13,三 十字链表 用来表示有向图. 有向图中,每一条边用一个结点表示,每个顶点也用一个结点表示.,firstin : 指向以该顶点为头的第一个边结点 firstout : 指向以该顶点为尾的第一个边结点 hlink : 指向头相同的下一条边 tlink : 指向尾相同的下一条边 tvpos,hvpos : 有向边两个顶点的位置,14,#define Max_V_num 20 /最大顶点数 typed

6、ef struct Arcnode /边结点类型 int tvpos,hvpos; struct Arcnode *hlink,tlink; Arcnode; typedef struct Vnode /顶点结点类型 vextype data; Arcnode *firstin,*firstout; Vnode; typedef struct Vnode vexs Max_V_num ; int vexnum,arcnum; Graphkind kind; graph,15,例如:,0,1,2,3,16,四 邻接多重表 用来表示无向图, 每一条边用一个结点表示,每个顶点也用一个结点表示.类似十

7、字链表.,data firstedge,顶点结点:,边结点:,mark vipos vilink vjpos vjlink,firstedge : 记录该顶点的第一个边结点 mark : 标记是否被搜索过 vipos,vjpos : 表示该边的两个顶点位置 vilink : 指向vi的下一条边 vjlink : 指向vj的下一条边,17,#define Max_V_num 20 /最大顶点数 typedef struct Arcnode /边结点类型 int mark; int vipos,vjpos; struct Arcnode *vilink,vjlink; Arcnode; typed

8、ef struct Vnode /顶点结点类型 vextype data; Arcnode *firstedge; Vnode; typedef struct Vnode vexs Max_V_num ; int vexnum,arcnum; graph,18,例如:,b,a,c,d,0,1,2,3,19,第四节 图的遍历,遍历方法,深度优先遍历 广度优先遍历,一 深度优先遍历( dfs) 算法思想: 1) 访问给定结点; 2) 重复对第一个未被访问的邻接点进行深度优先遍历, 直到不存在未被访问的邻接点结束. 可以用一个数组标识顶点是否被访问过. 示例解释:,20,void DFStraver

9、se(Graph G) for (v=0;vG.vexnum;+v) visitedv=FALSE; for (v=0;vG.vexnum;+v) /保证非连通图的遍历 if (!visitedv) DFS(G,v); void DFS(Graph G,int v) /连通图的遍历 visit(v);visitedv=TRUE; for (w= First_Adj(G,V);w;w=Next_Adj(G,v,w) if (!visitedw) DFS(G,w); ,21,二 广度优先遍历( bfs) 算法思想: 1) 访问给定结点v; 2) 由近至远,依次访问和 v 有路径相连且长度为 1,2

10、,3. 的顶点. 可以用一个数组标识顶点是否被访问过. 用一个队列存放刚访问过的结点.,示例解释:,22,void BFStraverse(Graph G) for (v=0;vG.vexnum;+v) visitedv=FALSE; iniqueue(Q); for (v=0;vG.vexnum;+v) /保证非连通图的遍历 if (!visitedv) visit(v);visitedv=TRUE;Enqueue(Q,v); while(!Queueempty(Q) Dequeue(Q,u); for (w= First_Adj(G,u);w;w=Next_Adj(G,u,w) if (!

11、visitedw) visit(w);visitedw=TRUE;Enqueue(Q,w); ,23,c,a,b,e,h,d,f,g,例如:,深度优先遍历: abdhecfg 广度优先遍历: abcdefgh,24,第五节 生成树 和最小生成树,一 生成树 一个连通图的生成树是由 n-1 条边且包含 G 的所有顶点的树组成. 可按深度或广度优先遍历来创建生成树.,例如:,深度 生成树1,广度 生成树2,25,c,a,b,e,h,d,f,g,假设采用孩子兄弟链表来表示生成树,则 P23 页 图的生成树 以及 孩子兄弟链表表示分别如下:,c,a,b,e,h,d,f,g,x,x,m,n,m,n,26

12、,void DFS_S_Tree(Graph G,CSTree /从 v 出发,建立以 q 为根的生成树 ,27,void DFS_Tree(Graph G,int v,CSTree /从 w 出发,建立以 q 为根的生成树 ,28,29,prim 算法: 1 设U=u0,T= ; 2 重复执行如下操作: 在所有 uU,v V-U的边 E中找一 条代价最 小的边 ,并入 T中, U=U+v 直到 U=V 或 T 中有n-1条边.,30,kruscal 算法: 1 设 G=(V,E);T=(v, ); 2 从 E中选一条最小权值的边,并从 E 中消除此边 3 若 属于T中不同的连通分量,则将加入

13、到 T 中,重复 2 ,直到T 中有n-1条边.,31,第六节 关键路径,定义:用顶点表示事件,而边表示完成事件所需时间,称这种有 向图为 AOE网.,材料,成品,顶点代表部件,边表示生产活动,整个图称为工程. 问题: 1完成工程至少需要多少时间? 2那些活动是影响进程的关键?,32,定义: 从起点到终点间的最长路径叫关键路径.关键路径上的时间之和即为工程所需的最少时间. 求关键路径的算法讨论 假设: Ve(i) 表示每个顶点的最早开始时间 VL(i) 表示每个顶点的最晚开始时间 t(i,j) 表示活动所需的时间 e(i,j) 表示活动最早开始时间 L(i,j) 表示活动最晚开始时间 存在如下

14、的关系: e(i,j)= Ve(i) L(i,j)= VL(j)- t(i,j) Ve(n)= VL(n),33,求Ve(i) 实质上是求 V1到Vi的最大路径. 求Ve(i)的算法: 1 令Ve(1) =0,i=2 2 Ve(i)=Max Ve(k)+t(k,i) | k为i 的直接前导 3 +i,重复 2直到 in 求 VL(i)的算法: 1 令VL(n) = Ve(n)0,i=n-1 2 VL(i)=Min VL(j)-t(i,j) | j为i 的直接后继 3 - -i,重复 2直到 i=0 求出Ve(i) ,VL(i) 后,就可以简单计算出e(i,j) , L(i,j) . 凡是e(i

15、,j) = L(i,j) 的边,即为关键路径上的边.,34,计算示例:,s1,s2,s3,s4,s6,s8,s9,s7,s5,5,4,5,1,1,2,9,7,4,2,4,0,0,5,5,6,15,17,13,9,5,7,6,15,17,13,7,5,4,关键路径为: S1S2S5S7S9 最短工期为: S1S2S5S8S9 17个时间单位,35,第六节 最短路径,设V0,V1,V2,.Vn -1为n个顶点序列 求V0到各顶点的最短路径. 例如:,V=V0,V1,V2,.Vn -1,36,Dijkstra 算法: 令 disti 表示已经求出的 v0 到 vi 的最短路径, S 表示已求出最短路径的顶点. 1)令 distv0 =0; disti= | i v0 S=v0; 2)求下一条最短路径: distj=Mindisti+costi,k | viS,vk V-S 3)令 S=S+vj; 重复2) 直到 S=V. Dijkstra 算法的中心思想是采用路径长度递增产生最短路径.,k,37,V0,v4,v1,v2,v3,10,30,10,20,0,10,50,3