数据结构与算法分析第九章 图论算法.pptVIP

第九章 图论算法 本章纲要 1.概念定义 2.拓扑排序 3.最短路径算法 4.网络流问题 5.最小生成树 6.深度优先有哪些信誉好的足球投注网站的应用 7.NP-完全性介绍 1.概念定义 飞机航空路线图 公路交通图 图 图G是由一个顶点集 V 和一个边集E构成的数据结构。 G = (V, E ) 1.概念定义 1.概念定义 1.概念定义 邻接 假若顶点v 和顶点w 之间存在一条边，则称顶点v 和w 互为邻接点，或v和w邻接。 顶点的度（degree） 与该顶点相关联的边的数目。 入度(in degree) 出度(out degree) 权 边上的值 1.概念定义 路径 构成首尾相连的一系列边的顶点集合。 例如路径w1,w2,w3,…,wN (wi,wi+1) E,0iN 路径长=边数=N-1 环 简单路径 顶点不重复出现的路径，但第一个顶点和最后一个顶点可能相同。 1.概念定义 圈 w1=wN，长度至少为1的一条路径； 该路径若是简单路径，该圈就是简单圈。 无向图中，圈的边是互异的 无圈的有向图，称为DAG 1.概念定义 连通：顶点v至w之间有路径存在 连通图：无向图 G 的任意两点之间都是连通的，则称 G 是连通图。 连通分量：极大连通子图 1.概念定义 连通：顶点v至v’’之间有路径存在 强连通图：有向图 G 的任意两点之间都是连通的，则称 G 是强连通图。 强连通分量：极大连通子图(每个子图是强连通的) 基础图：有向图去掉弧上方向形成的无向图 弱连通图：非强连通但其基础图是连通的有向图。 1.概念定义 生成树 极小连通子图。包含图的所有 n 个结点，但只含图的 n-1 条边。 完全图 每一对顶点间都存在一条边。 1.概念定义 图的四种常用的存储形式： 邻接矩阵和加权邻接矩阵（labeled adjacency matrix） 邻接表 十字链表 邻接多重表 1.概念定义 1.概念定义 1.概念定义 1.概念定义 1.概念定义 1.概念定义 1.概念定义 2.拓扑排序 下图表示课程之间的依赖关系。根据该图排一张学习的先后次序表。 1,2,3,4,5,6,7 2.拓扑排序 先决条件问题。 拓扑排序（topological sort） 将一个有向无圈图中所有顶点在不违反先决条件关系的前提下排成线性序列的过程称为拓扑排序 2.拓扑排序 拓扑序列 对于有向无圈图G=（V，E），V里顶点的线性序列称作一个拓扑序列，如果该顶点序列满足： 若在有向无圈图G中从顶点Vi到Vj有一条路径，则在序列中顶点Vi必在顶点Vj之前。 2.拓扑排序 任何有向无圈图，其顶点都可以排在一个拓扑序列里，其拓扑排序的方法是： （1）从图中选择一个入度为0的顶点且输出之。 （2）从图中删掉此顶点及其所有的出边。 （3）回到第（1）步继续执行。 2.拓扑排序 拓扑排序 简单方法 O(|V|2) 队列实现 图9-6 O(|E|+|V|) 3.最短路径算法 赋权路径长 路径上所有权值之和 无权路径长 路径长：边数之和 3.最短路径算法 单源最短路径（single-source shortest paths） 指的是对已知图G=（V，E），给定源顶点s∈V，找出s到图中其它各顶点的最短路径。 每对顶点间的最短路径（all-pairs shortest paths） 指的是对已知图G=（V，E），任意的顶点Vi，Vj∈V，找出从Vi到Vj的最短路径。 3.最短路径算法 3.最短路径算法 无权最短路径 见图9-10 S为v3 广度优先有哪些信誉好的足球投注网站 按层次处理顶点：距源点近的顶点先被访问，远的顶点后被访问。 类似树的层序遍历 3.最短路径算法 队列实现 O(|E|+|V|) 3.最短路径算法 赋权最短路径 见图9-20，源点v1 最短路径的子路径仍是最短路径 Dijkstra算法 把图中所有顶点分成两组 第一组包括已确定最短路径的顶点 第二组包括尚未确定最短路径的顶点； 按最短路径长度递增的顺序逐个把第二组的顶点加到第一组中去 直至从s出发可以到达的所有顶点都包括进第一组中。 3.最短路径算法 在这个过程中，总保持从s到第一组各顶点的最短路径长度都不大于从s到第二组的任何顶点的最短路径长度，而且，每个顶点都对应一个距离值： 第一组的顶点对应的距离值就是从s到该顶点的最短路径长度 第二组的顶点对应的距离值是从s到该顶点的只包括第一组的顶点为中间顶点的最短路径长度 3.最短路径算法 例子： 见图9-28 3.最短路径算法 无圈图 工程最快进度问题 工程包含很多任务，任务之间存在依赖关系 完成每一项任务需要一定的时间 该工程的最早完成时间？ 动作节点图 事件节点图 3.最短路径算法 3.最短路径算法 工程最早完成时间 关键路径 从第一个事件到最