数据结构-C语言描述(第三版)第10章图.ppt

图10－24 10－4 已知有向图的邻接表，试写出计算各顶点的入度的算法。 10－5 设计一个函数，它实现从一个二维数组表示的图的邻接矩阵建立该图的邻接表的功能。 10－6 在图10－24所建立的邻接表上进行以顶点2为起始顶点的深度优先有哪些信誉好的足球投注网站和宽度优先有哪些信誉好的足球投注网站。分别画出遍历所得到的深度优先有哪些信誉好的足球投注网站和宽度优先有哪些信誉好的足球投注网站的生成森林(或生成树)。 10－7 适当修改程序10－5和10－6的图的深度优先和宽度优先有哪些信誉好的足球投注网站函数，使之能在邻接表上求有向图的深度优先有哪些信誉好的足球投注网站和宽度优先有哪些信誉好的足球投注网站的生成森林(生成树)。 10－8 一个有向无环图(DAG)的根结点是指某个结点R，通过从它出发的有向路径可以到达DAG的任意一个结点。设计一个算法使之以一个有向图作为输入，若该图有一个根，请确定此图的根结点。 10－9 分别设计算法，在邻接矩阵上实现有向图的深度优先有哪些信誉好的足球投注网站和宽度优先有哪些信誉好的足球投注网站。 10－10 设图以邻接表存储，设计一个算法，确定一个有n个顶点的有向图是否包含回路。 10－11 设某项工程由图10－25所示的工序组成。若各工序以流水方式进行(即串行进行)。 (1) 画出该工程的AOV网络； (2) 给出该工程的全部合理的工程流程。 图中的紧前工序是指，设有工序A和B，若工序B必须在工序A完成后才能开始，则工序A称为工序B的紧前工序。 图10－25 10－12 设有边集合：0，1，1，2，4，1，4，5，5，3，2，3， (1) 求此图的所有可能的拓扑序列； (2) 若以此顺序通过加入边的方式建立邻接表，则在该邻接表上执行程序10－8的拓扑排序算法(TopoSort)，将得到何种拓扑序列？ 10－13 设AOE网如图10－26所示。求各事件的可能的最早发生时间和允许的最迟发生时间，各活动可能的最早开始时间和允许的最晚开始时间，以及关键活动和关键路径及其长度。 图10－26 10－14 使用普里姆算法以1为源点，画出图10－27的无向图的最小代价生成树。 10－15 使用克鲁斯卡尔算法，画出图10－27的无向图的最小代价生成树。 10－16 证明：如果一个无向图中，所有的边的代价均不相等，那么只存在一棵最小代价生成树。 10－17 现以邻接矩阵表示带权无向图，请实现普里姆算法。 图10－27 10－18 用迪杰斯特拉算法求图10－28的有向图中以顶点A为源点的单源最短路径。写出一维数组d和path在执行该算法的过程中各步的状态。 10－19 用弗洛伊德算法求图10－28的有向图的所有顶点之间的最短路径。写出二维数组d和path在执行该算法的过程中各步的状态。 10－20 试设计一个算法，由用弗洛伊德算法生成的二维数组path打印所有顶点之间的最短路径。 10.6.1 单源最短路径 1. 迪杰斯特拉算法 单源最短路径问题是：给定带权的有向图G=(V, E)，源点v(V，求从v到V中其余各顶点的最短路径。图10－17(a)的有向图从顶点0到其余各顶点的最短路径被列表于图10－17(b)中。 图10－17 单源最短路径示例 (a) 带权的有向图G；(b) (a)中图G的顶点0的单源最短路径 如何求这些最短路径呢？迪杰斯特拉提出了按路径长度的非递减次序逐一产生最短路径的算法：首先求得长度最短的一条最短路径，再求得长度次短的一条最短路径，依此类推，直到从源点到其他所有顶点之间的最短路径都已求得为止。 具体做法是：设集合S存放已经求得最短路径的终点。初始状态时，集合S中只有一个源点，设为顶点v0。以后每求得一条最短路径(v0, v1, …, vt)，便将终点vt加到集合S中去，直到全部顶点都已加到S中，算法结束。 我们用一维数组d保存各条最短路径的长度，其中，d[i]存放从顶点v0到顶点vi的最短路径的长度。在算法执行中，若vi是尚未产生最短路径的顶点，则d[i]被定义为“由已经产生的最短路径上再扩充一条边”所形成的从v0到vi的“当前最短路径”。换句话说，d[i]中存放的是从源点v0起，中间只经过集合S中的结点而达到vi的所有可能路径中的最短路径的长度。 初始状态下，集合S中只有一个源点v0，S={v0}，则 (10－3) 其中，w(0, i)是边v0, vi的权值。 设图中从v0开始到所