数据结构：思想与方法-翁惠玉-第十二章.pptVIP

* 图遍历的应用 无向图的连通性 欧拉回路 有向图的连通性 拓扑排序 * 拓扑排序 设G=（V，E）是一个具有n个顶点的有向无环图。V中的顶点序列V1，V2，…，Vn称为一个拓扑序列，当且仅当该序列满足下列条件：若在G中，从Vi到Vj有一条路径，则序列中Vi必须排在Vj的前面。 * 下述集合 M 代表课程的集合 1 代表数学， 2 代表程序设计， 3 代表离散数学， 4 代表汇编程序设计， 5 代表数据结构， 6 代表结构化程序设计, 7 代表编译原理 关系R表示课程学习的先后关系，如数学必须在离散数学之前学习。要求排一张学习的先后次序表。 拓扑排序的应用 * 1 3 2 7 5 6 4 数学 程序设计 离散数学 汇编程序设计 数据结构 结构化程序设计 编译原理 用有向图表示关系R。节点集为课程集合。如果课程i和j有关系R，则有一条边。 * 可行的排课： 方案1： 1，2，3，4，5，6，7 方案2： 1，2，3，5，6，4，7 方案3： 1，2，3，5，6，7，4 。。。 1 3 2 7 5 6 4 数学 程序设计 离散数学 汇编程序设计 数据结构 结构化程序设计 编译原理 * 找出拓扑排序的过程 第一个输出的结点（序列中的第一个元素）： 必须无前驱，即入度为0 后驱：必须等到它的前驱输出之后才输出。 无前驱及后件的结点：任何时候都可输出。 逻辑删除法：当某个节点被输出后，就作为该节点被删除。所有以该节点作为前驱的所有节点的入度减1。 * 1 3 2 7 5 6 4 数学0 程序设计1 离散数学1 汇编程序设计1 数据结构2 结构化程序设计1 编译原理3 * 0 0 0 1 1 1 汇编程序设计 0 0 1 1 1 结构化程序设计 0 1 2 2 数据结构 0 1 2 2 3 3 编译原理 0 0 1 程序设计 0 1 离散数学 0 数学 输出： 数学， 离散数学， 程序设计， 数据结构， 结构化程序设计， 编译原理， 汇编程序设计 * 拓扑排序的实现 计算每个结点的入度，保存在数组inDegree中； 检查inDegree中的每个元素，将入度为0的结点入队； 不断从队列中将入度为0的结点出队，输出此结点，并将该结点的后继结点的入度减1；如果某个邻接点的入度为0，则将其入队。 * template class TypeOfVer, class TypeOfEdge void adjListGraphTypeOfVer, TypeOfEdge::topSort( ) const { linkQueueint q; edgeNode *p; int current, *inDegree = new int[Vers]; for (int i = 0; i Vers; ++i) inDegree[i] = 0; for ( i = 0; i Vers; ++i) for (p = verList[i].head; p != NULL; p = p-next) ++inDegree[p-end]; } for (i = 0; i Vers; ++i) if (inDegree[i] == 0) q.enQueue(i); cout 拓扑排序为： endl; while( !q.isEmpty( ) ){ current = q.deQueue( ); cout verList[current].ver \t; for (p = verList[current].head; p != NULL; p = p-next) if( --inDegree[p-end] == 0 ) q.enQueue( p-end ); } cout endl; } * 时间复杂度 如果图以邻接表表示 计算入度需要O（|V|+|E|）的时间，有哪些信誉好的足球投注网站入度为0的结点需要O（|V|）的时间。每个结点入一次队、出一次队。每出一次队，需要检查它的所有后继结点，因此也需要O（|V|+|E|）的时间。所以总的执行时间也是O（|V|+|E|） * 总结 图是一种最一般的数据结构，有着广泛的用途。 图可以用邻接矩阵、邻接表和其他方法来存储 图的遍历：深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站，并给出了它们在邻接表的存储方式下的实现。 图的应用： 检测无向图的连通性 寻找无向图的欧拉回路 寻找有向图的强连通分量 拓扑排序 * * * * * * * * * * * * * * 广度优先有哪些信誉好的足球投注网站的实现 需要记录每个结点是否已被访问 需要记住每个已被访问的结点的后继结点，然后依次访问