Ch_7图(数据结构).ppt

七桥问题 网络路由问题 要求 掌握图的各种存储结构及其构造算法。 熟练掌握图的两种有哪些信誉好的足球投注网站路径的遍历：遍历的逻辑定义、深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站的算法。 应用图的遍历算法求解各种简单路径问题。 图的抽象数据类型定义 ADT Graph{ 数据对象v：v是具有相同特性的数据元素的集合，称为顶点。 数据关系R={VR} VR＝{v,w| v,w∈V 且 P(v,w)} v,w表示从 v 到 w弧， 谓词 P(v,w) 定义了弧 v,w的意义或信息。 讨论2 ：有向图的邻接矩阵表示。 讨论3 ： 有权图（即网络）的邻接矩阵表示。 邻接表存储法的特点： 讨论：邻接表与邻接矩阵有什么异同之处？ 例：画出有向图的十字链表。 知识回顾 图的定义 图的存储 知识回顾 知识回顾 知识回顾 知识回顾 知识回顾 知识回顾 知识回顾 深度优先有哪些信誉好的足球投注网站（遍历）步骤： 连通图的深度优先遍历算法 递归算法 算法分析 对每个顶点至多调用一次DFS函数。遍历图的过程实质上是对每个顶点查找其邻接点的过程。 采用二维数组：O(n2) 采用邻接表：O(n+e) 广度优先有哪些信誉好的足球投注网站（遍历）步骤： 最小树MST性质 假设N=(V,{E})是一个连通图，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u ∈U, v∈V-U，则必存在一颗包含边(u,v)的最小生成树。 知识回顾 图的遍历 DFS BFS 图的最小生成树 问题1 几乎所有工程都可分为若干个称为活动的子工程，而这些子工程之间，通常受一定条件的约束，如某些子工程的开始必须在另一子工程完成之后。 关心两方面问题： 1、工程能否顺利进行。 2、估算整个工程完成必须的最短时间。 AOV网——用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex network)，简称AOV网 AOV网中不允许有回路 “事件(顶点)Vi” 的 最早发生时间 ve(i) ve(i) = 从源点到顶点i的最长路径长度； 此时间决定了所有以Vi为尾的弧所表示的活动的最早开始时间。 e(i)—表示活动ai的最早开始时间。 l(i) —表示活动ai的最迟开始时间。 l(i)-e(i) —活动ai的时间余量。 关键活动： l(i)=e(i)的活动。 关键路径上的所有活动都是关键活动。 提前完成非关键活动不能加快工程的进度。 从Ve[0] = 0开始，向前递推 Vi, Vj ? S2, i = 1, 2, ?, n-1 其中, S2是所有从Vi指向顶点Vj 的有向边 Vi , Vj的集合。 从Vl[n-1] = Ve[n-1]开始，反向递推 Vi, Vj ? S1, i = n-2, n-3, ?, 0 其中, S1是所有从顶点Vi 发出的有向边 Vi , Vj 的集合。 知识回顾 拓扑排序 关键路径 7.6 两点之间的 最短路径问题 7.6 两点之间的 最短路径问题 求从某个源点到其余各点的最短路径 算法实现 图用邻接矩阵存储 length[][]存放最短路径长度 path[i][j]是从Vi到Vj的最短路径上Vj前一顶点序号 算法描述 作业一 7.1 7.14(选做) 作业二 给出下面有向图的十字链表存储结构。 作业三 7.9 7.10 作业四 7.11 7.13 Status CriticalPath(ALGraph G){ //G为有向图,输出G的各项关键活动 if(!TopologicalOrder(G,T))return ERROR;//有回路 vl[0..G.vexnum-1]=ve[G.vexnum-1]; //初始化顶点事件的最迟发生时间 while(!StackEmpty(T)) //按拓扑逆序求各顶点的vl值 for(Pop(T,j),p=G.vertices[j].firstarc;p;p-nextarc) { k=p-adjvex; dut=*(p-info);//dutj,k if(vl[k]-dutvl[j]) vl[j]=vl[k]-dut; }//for for(j=0;jG.vexnum;++j) //求e,l和关键活动 for(p=G.vertices[j].firstarc;p;p=p-nextarc) { k=p-adjvex; dut=*(p-info); e=ve[j]; l=vl[k]-dut; tag=(e==l)?’*’:’’; printf(j,k,dut,e,l,tag); //输出关键活动