第8章_图的应用讲述.ppt

第八章 图的应用 8.1 图的生成树和最小生成树 8.1.1 概念 图的生成树：用最少的边刚好使图能够连通而生成的图（无回路，不唯一） 8.1.3 克鲁斯卡尔算法 思路：不需要选择出发点，按边的权值从小到大选择各边,若某边选中后出现回路,则 舍去该边，直到将所有顶点连通。 最小生成树不一定唯一：当出现权值相等的边，且任选一边均可以构成最小生成树时，则不唯一 练习： 1.P302习题8-1中第1题 普里姆算法： (v0,v1)6 (v1,v6)4 (v6,v2)9 (v2,v3)5 (v3,v4)10 (v0,v5)12 克鲁斯卡尔算法： (v1,v6)4 (v2,v3)5 (v1,v0)6 (v2,v6)9 (v3,v4)10 (v0,v5)12 2.已知世界六大城市为：北京（B）、纽约（N）、巴黎（P）、伦敦（L）、东京（T）、墨西哥城（M）。试在由下表给出的交通网中确定最小生成树。 世界六大城市交通里程网络表（单位：100km） B N P L T M B 109 82 81 21 124 N 109 58 55 108 32 P 82 58 3 97 92 L 81 55 3 95 89 T 21 108 97 95 113 M 124 32 92 89 113 8.2 最短路径 对于无权图，从一顶点到另一顶点经过边数最少的那条路径称为最短路径，其路径长度称为最短路径长度。 8.2.2 从一顶点到其余各顶点的最短路径 对于一个具有n个顶点和e条边的图G，从某一顶点vi(源点)到其余任一顶点vj(终点)的最短路径，可能是它们之间的边(i,j)或i,j,也可能是经过k个(1≤k≤n-2)中间顶点和k+1条边构成的路径 练习： 1.图的遍历：从V1顶点出发遍历下图 克鲁斯卡尔(Kruskal)算法 8.2.3 每对顶点间的最短路径 分别以图中每个顶点作为源点共n次调用狄克斯特拉算法，时间复杂度O(n3); 弗洛伊德(Floyd)算法,时间复杂度O(n3);但较为简单 3.各村庄之间距离如下邻接矩阵所示。 （1）若建一家医院，问建在哪个村庄能使各村庄总体交通代价最小？ （2）若建一个消防站呢？ 8.3 拓扑排序 一个较大的工程往往被划分为许多子工程，我们将这些子工程称为活动(activity)。 在整个工程中，某些活动的开始必须以其它所有前序活动的结束为先决条件。 我们将这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network),简称AOV网。 8.4 关键路径 AOE网：用边表示活动的网(Activity On Edge network)。通常用它表示一个工程的进度。 活动：子工程，整个工程的一部分 AOE网中，图中的边表示活动，边上的权值表示活动的持续时间，或者完成活动的代价 特点：持续一段时间 事件：图中的顶点表示事件，它是活动间的转折点，表示它的所有入边活动到此完成，所有出边活动从此开始。 特点：瞬间发生 AOE网络在某些工程估算方面非常有用。例如，可以使人们了解： (1) 完成整个工程至少需要多少时间(假设网络中没有环)? (2) 哪些活动是影响工程进度的关键? 关键活动：开始时间余量为0的活动 关键路径：由关键活动所形成的从源点到汇点的每一条路径，即源点到汇点之间具有最长路径长度的路径。 求关键路径步骤 求Ve(i) 求Vl(j) 求e(i) 求l(i) 计算l(i)-e(i) 3.P303 第7题 4.下表给出了某工程各工序之间的优先关系和各工序所需时间 （1）画出相应的AOE网 （2）列出各事件的最早发生时间,最迟发生时间 （3）找出关键路径并指明完成该工程所需最短时间. 【武汉交通科技大学 1996 二、6 (7分)】 使拓扑排序结果唯一的算法： 1.按结点序号从小到大的