第7章数据结构中的图课件.pptVIP

数据结构与应用 内容简介 教材目录 第7章 图 7.1.1图的定义 1. 迪杰斯特拉(Djikstra)算法基本思想 迪杰斯特拉提出了按路径长度递增的次序逐一产生最短路径的算法： 首先求得长度最短的一条最短路径，再求得长度次短的一条最短路径，依此类推，直到从源点到其它所有顶点之间的最短路径都已求得为止。 设集合S存放已经求得最短路径的终点，则V-S为尚未求得最短路径的终点。初始状态时，集合S中只有一个源点，设为顶点v0。迪杰斯特拉算法的具体做法是：首先产生从点v0到自身的路径，其长度为0，将v0加入S；算法的每一步上，按照最短路径值的递增次序，产生下一条最短路径，并将该路径的终点vj∈V-S加入S；直到S=V，算法结束。 2. 算法描述 3. 算法实现 教材sf7_22.cpp 7.5.2所有顶点对之间的最短路径 1. 弗洛伊德算法思想 求从顶点vi到 vj的最短路径。设集合S的初始状态为空集合。然后，依此向集合S中加入顶点v0，v1，v2…vn-1，每次加入一个顶点。用二维数组dist保存各条最短路径的长度，其中，dist[i][j]为从i到j的当前最短路径长度。随着S中的顶点的不断增加，dist[i][j]的值不断修正，当S=V时，dist[i][j]的值就是从i到j的最短路径。 2. 算法描述 图7.24 用弗洛伊德算法求带权有向网所有顶点对的最短路径 3. 算法实现 教材sf7_23.cpp 7.6 DAG图及其应用 一个无环的有向图称作有向无环图，简称DAG图。DAG图是一类比有向树更一般的特殊有向图。 7.6.2 AOV网与拓扑排序 1．AOV网 以有向图中的顶点表示活动，弧表示活动之间的优先关系，这样的有向图称为顶点表示活动的网，简称AOV网。 2．拓扑排序 设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v0，v1，…，vn-1称为一个拓扑序列，当且仅当满足下列条件：若从vi到顶点vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。对一个有向图构造拓扑序列的过程称为拓扑排序。 3．拓扑排序的实现 教材sf7_24.cpp 7.6.3 AOE网与关键路径 1. AOE网 与AOV网对应的是AOE(Activity On Edge)网，即边表示活动的网。在AOV网中，有向图的顶点表示一项任务，有向边表示任务之间的先后关系。在实际应用中，任务之间除了先后关系外，还有时间上的约束，用AOE网来表示这种约束关系。 2．关键路径 在AOE网中，因为有些活动可以同时进行，所以完成一个工程所需的最短时间是从一个始点到一个终点的最大路径长度。具有最大长度的路径被称为关键路径(critical path)。 3．关键路径的确定 教材sf7_25.cpp 基于邻接矩阵存储结构的图的类模板定义cx7_1.h 邻接矩阵的基本操作及其实现: 1．求顶点在图中的位置 2．创建图 3．顶点的增删 4．弧的增删 5．输出邻接矩阵 6．销毁有向图 7.2.2 邻接表 邻接表表示法是图的一种链接存储结构，类似于树的孩子链表表示法。 对于图G中的每个顶点vi，该方法把所有邻接于vi的顶点链成一个单链表，这个单链表就称为顶点vi的邻接表，邻接表中每个结点有两个域：其一是邻接点域(adjvex)，用以存放与vi相邻接的顶点vj的序号j；其二是链域(next)，用来指示与vi相邻接的下一顶点，从而将邻接表的所有表结点链在一起。 为每个顶点vi的邻接表设置一个头结点，头结点中包含两个域，其中一个是顶点域vertex，用来存放顶点vi的数据信息；另一个是指针域firstedge，它指向vi的邻接表的开始结点，相当于vi的邻接表的头指针。为了便于随机访问任一顶点的邻接表，将所有头结点顺序存储在一个一维数组中，称为顶点表，将其中的头结点称为顶点表结点。这样就构成了图的邻接表表示。 邻接表的基本操作及其实现: 求顶点在图中的位置 创建有向图 顶点的增删 弧的增删 输出邻接表 销毁有向图 7.2.3 邻接矩阵和邻接表的比较 7.3 图的遍历 图的遍历是指从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次的操作。 7.3.1 深度优先有哪些信誉好的足球投注网站遍历 深度优先有哪些信誉好的足球投注网站(DFS) 遍历类似于树的先序遍历。假定给定图G的初态是所有顶点均未曾访问过。则从图中某顶点v出发进行深度优先有哪些信誉好的足球投注网站遍历的基本思想是： (1) 访问顶点v； (2) 从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先有哪些信誉好的足球投注网站遍历； (3) 重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。 从图中某顶点v出发，基于邻接矩阵表示的深度优先有哪些信誉好的足球投注网站的递归过程如程序sf7_13.cpp所示