综合数据结构07解决方案.ppt

*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;1. 区别： ① 对于任一确定图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。 ② 邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。 2. 用途：邻接矩阵多用于稠密图；而邻接表多用于稀疏图;*;*;*;*;a;*;*;*;V;*;*;*;*;*; * ; (连通网的)最小生成树;*;*;*;*;*; 在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。;*; 设置两个辅助数组，对当前V－U集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边： 对于每一个顶点v∈V-U，closest[v]为U中距离v最近的一个邻接点，即边 (v，closest[v]) 是在所有与顶点v相邻、且其另一顶点j∈U的边中具有最小权值的边，其最小权值为lowcost[v]，即;a;普里姆算法;*;*;*;*; 求从源点到其余各点的最短路径的算法的基本思想:; 在这条路径上，必定只含一条弧，并且这条弧的权值最小。 ;其余最短路径的特点：;求最短路径的迪杰斯特拉算法：;1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。;*;*;*;*;*;*;*;求每一对顶点之间的最短路径;若vi,vj存在，则存在路径{vi,vj} // 路径中不含其它顶点 若vi,v1,v1,vj存在，则存在路径{vi,v1,vj} // 路径中所含顶点序号不大于1 若{vi,…,v2}, {v2,…,vj}存在， 则存在一条路径{vi, …, v2, …vj} // 路径中所含顶点序号不大于2 …;*;*;*;;*;*;*;何谓“拓扑排序”？;例如：对于下列有向图;B;*;如何进行拓扑排序？;a;*;*;*;取入度为零的顶点v; while (v0) { printf(v); ++m; w:=FirstAdj(v); while (w0) { inDegree[w]--; w:=nextAdj(v,w); } 取下一个入度为零的顶点v; } if mn printf(“图中有回路”);; 为避免每次都要有哪些信誉好的足球投注网站入度为零的顶点， 在算法中设置一个“栈”，以保存“入度为零”的顶点。;*;*;*;*;*;*;a; 如何求关键活动？; 假设第 i 条弧为 j, k 则 对第 i 项活动言 “活动(弧)”的 最早开始时间 ee(i) ee(i) = ve(j)； “活动(弧)”的 最迟开始时间 el(i) el(i) = vl(k) – dut(j,k)；; 事件发生时间的计算公式： ve(源点) = 0； ve(k) = Max{ve(j) + dut(j, k)} vl(汇点) = ve(汇点)； vl(j) = Min{vl(k) – dut(j, k)};a;0;*;*