g-k四川大学计算机软件.ppt

Chapter 6Graphs 一个连通图G如果不是重连通图， 那么它可以包括几个重连通分量 若依次删除一个连通图中的 1, 2, …, k-1 个顶点后,该图仍连通,删除第k个顶 点后该图成为不连通的,则称该图的 连通度为k 　　在有向图中, 统计第 i 行 1 的个 数可得顶点 i 的出度，统计第 j 列 1 的个数可得顶点 j 的入度 　　在无向图中, 统计第 i 行 (列) 1 的个数可得顶点i 的度 图的遍历 深度优先遍历 DFS (Depth First Search)　 广度优先遍历 BFS (Breadth First Search) 深度优先遍历DFS(Depth First Search) 深度优先遍历的示例 广度优先遍历BFS(Breadth First Search) 广度优先遍历的示例 最小代价生成树(minimum cost spanning tree) 构造最小生成树的准则 必须使用且仅使用该网络中的n-1 条边来联结网络中的 n 个顶点 不能使用产生回路的边 各边上的权值的总和达到最小 活动网络 ( Activity Network ) 对学生选课工程图进行拓扑排序, 得到的拓扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6 在算法中, 使用一 个堆栈或队列存放入度 为零的顶点, 供选择和 输出无前驱的顶点 在算法中, 使用一 个堆栈或队列存放入度 为零的顶点, 供选择和 输出无前驱的顶点 拓扑排序算法描述 建立入度为零的顶点栈 当入度为零的栈不空时, 重复执行 从栈中退出一个顶点, 并输出之 从AOV网中删去这个顶点和它发出的边, 边的终点入度减一 如果边的终点入度减至0, 则该顶点进入入度为零的顶点栈 如果输出顶点个数少于AOV网的顶点个数, 则报告网络中存在有向环 建立入度为零的顶点队 当入度为零的队不空时, 重复执行 从队中退出一个顶点, 并输出之 从AOV网中删去这个顶点和它发出的边, 边的终点入度减一 如果边的终点入度减至0, 则该顶点进入入度为零的顶点队 如果输出顶点个数少于AOV网的顶点个数, 则报告网络中存在有向环 在算法实现时, 为了建立入度为零的顶点栈,可以不另外分配存储空间, 直接利用入度为零的顶点的count[ ]数组元素。设立一个栈顶指针 top, 指示当前栈顶位置, 即某一个入度为零的顶点。栈初始化时置top = -1 将顶点i 进栈时执行以下指针的修改： count[i] = top; top = i ; // top指向新栈顶i, 原栈顶元素在count[i]中 退栈操作可以写成： j = top; top = count[top]; //位于栈顶的顶点记于 j, top退到次 栈顶 if ( --count[k]==0 ) //顶点入度减一 { count[k]=top; top=k; } //顶点的入度减至零, 进栈 p = p-link; } } } 完成整个工程所需的时间取决于从源点到汇点的最长路径长度, 即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径 ve(源点) = 0； ve(k) = Max{ve(j) + dut(j, k)} (2=k=n, j, k属于所有以k为 头的弧的集合) vl(汇点) = ve(汇点)； vl(j) = Min{vl(k) – dut(j, k)} (1=j=n-1, j, k属于所有以j为 尾的弧的集合) ee(i) = ve(j) el(i) = vl(k) – dut(j,k) ve(源点) = vl(源点) = 0 vl(汇点) = ve(汇点) 关键活动:el(i) = ee(i) 这两个递推公式的计 算必须分别在拓扑有序及 逆拓扑有序的前提下进行 最短路径 (Shortest Path) 最短路径问题 如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小