四川大学数据结构第7章 图.pptVIP

数据结构与算法(C++版) 第7章 图 　　在有向图中, 统计第i行 1 的个数可得顶点vi 的出度，统计第j列1的个数可得顶点vj 的入度 　　在无向图中, 统计第i 行 (列)1的个数可得顶点vi 的度 7.4 图的最小代价生成树 构造最小生成树的准则 必须使用且仅使用连接无向该网中的n-1 条边来通结连通无向网中的 n 个顶点 必须没有长度大于2的简单回路 各边上的权值的总和达到最小 对学生选课关系图进行拓扑排序, 得到的拓扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6 建立入度为零的顶点队列(或栈) 入度为零的队列(或栈)不空时, 重复执行 从队列(或栈)中退出一个顶点, 并输出之 从有向图中删去这个顶点和它发出的边, 边的终点入度减一 如果边的终点入度减至0, 则该顶点进入入度为零的顶点队列(或栈) 如果输出顶点个数少于有向图的顶点个数, 则报告图中存在有向环 完成整个工程所需的时间取决于从源点到汇点的最长路径长度, 即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径 ve源点= 0； vek= Max{vej+ net.GetWeight(j, k)} (2≤k≤n, vj,vk属于所有以vk为 终点的边的集合) vl汇点= ve汇点； vlj = Min{vlk – net.GetWeight(j, k)} (1≤j≤n-1, vj,vk属于所有以vj为 起点的边的集合) eejk = vej eljk = vlk– net.GetWeight(j, k) ve源点 = vl源点 = 0 vl汇点 = ve汇点 关键活动:eljk = eejk 这两个递推公式的计算必须分别在拓扑有序序列及拓扑逆有序序列的前提下进行 7.6 最短路径 (Shortest Path) 最短路径问题:如果从有向网中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小 一、单源点最短路径问题 ——Dijkstra算法 为求得这些最短路径, Dijkstra提出按路径长度的递增次序, 逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点vs到其它各顶点的最短路径全部求出为止 二、所有顶点之间的最短路径 ——Floyd算法 5. 扑拓排序算法的描述 template class ElemType StatusCode TopSort(const AdjMatrixDirGraphElemType g) // 初始条件：存在有向图g // 操作结果：如g无回路,则输出g的顶点的一个拓扑序列, // 并返回SUCCESS,否则返回FAIL { int *indegree = new int[g.GetVexNum()]; //入度数组 LinkQueueint q; // 队列 int count = 0; StatIndegree(g, indegree); // 统计顶点的入度 for (int v = 0; v g.GetVexNum(); v++) { // 遍历顶点 if (indegree[v] == 0) q.InQueue(v);// 建立入度为0的顶点队列 } 6. 扑拓排序算法的实现 while (!q.Empty()) { // 队列非空 int v1; q.OutQueue(v1); // 取出一个入度为0的顶点 cout v1 ; count++; // 对输出顶点进行记数 for (int v2 = g.FirstAdjVex(v1); v2 != -1; v2 = g.NextAdjVex(v1, v2)) { // v2为v1的一个邻接点 if (--indegree[v2] == 0)//邻接点入度减1 q.InQueue(v2);//入度为0,v2入队 }; } } delete []indegree; // 释放indegree所占用的存储空间 if (count g.GetVexNum()) return FAIL; // g有回路 else return SUCCESS; // 拓扑排序成功 } 二、关键路径(Critical Path) 1. 问题的提出的相关概念 问题: 　　　假设以有向网表示一个施工流程