二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(21)

if ( ! visited[w] ) {

visit ( w ); visited [w] = true;

EnQueue ( Q, w );}}} }

时间复杂度分析

观察搜索树可以看出，无论是深度优先搜索还是广度优先搜索，其搜索过程就是对每个顶点求所有邻接点的过程。当用邻接表存储图时，其时间复杂度为O(n+e)；当采用邻接矩阵作

2

为存储结构时，时间复杂度是O(n) (因为求一个顶点的所有邻接点就是搜索邻接矩阵的一

2

行中的n个数，而顶点的个数为n，总共就是n)。 最小生成树

最小生成树及MST性质 最小生成树。MST性质。

注意：同一个连通网的最小生成树可能是不唯一的，但其代价都是最小(唯一的)。 克鲁斯卡尔算法

18

一句话，“不构成环的情况下，每次选取最小边”。

(a) 无向网

(b)-(e) 克鲁斯卡尔算法计算最小生成树(f) 得到的最小生成树

(g) 另一个可能的最小生成树

提示：在不要步骤、只要结果的情况下可采用，边较少时特别有效。 普里姆算法

记V是连通网的顶点集，U是求得生成树的顶点集，TE是求得生成树的边集。 普里姆算法：

18

不准确的说法，只为便于理解和记忆，不要在正式场合引用。

(a) 开始时，U={v0}，TE=Φ；

(b) 计算U到其余顶点V-U的最小代价，将该顶点纳入U，边纳入TE； (c) 重复(b)直到U=V。

例：用普里姆算法计算下图的最小生成树。

特点

只与顶点个数n有关 与边的数目e无关 适用于稠密图

只与边的数目e有关 与顶点个数n无关 适用于稀疏图

拓扑排序

有向无环图(DAG)，AOV网；拓扑排序。

19

拓扑排序，一句话“每次删除入度为0的顶点并输出之”。

例：以下DAG图拓扑排序的结果是：ABCDE。 注意：拓扑排序的结果不一定是唯一的。如：AE也是以上DAG图的拓扑有序序列。 关键路径

AOE网，关键路径

AOE 网(活动在边上)，边代表活动或任务，顶点代表事件。 事件i发生后，其后继活动a(i,*)都可以开始；只有所有先导活动a(*,j)都结束后，事件j才发生。

关键路径算法

问题：a) 整个工程完工需要多长时间？ b) 哪些活动影响工程的进度？或求关键路径。 事件(顶点) i： 最早发生时间ve(i)，最晚发生时间vl(i)； 活动(边) a(i,j)： 最早开始时间e(i,j)，最晚开始时间l(i,j)。

于是，整个工程完工的时间就是终点的最早发生时间；关键路径就是路径长度最长的路径。 19

不准确的说法，只为便于理解和记忆，不要在正式场合引用。

求关键路径的算法：

(a) 按拓扑有序排列顶点：对顶点拓扑排序； (b) 计算ve(j)：

?ve(1)?0,其中*为任意前驱事件； ?

?ve(j)?max{ve(*)?a(*,j)}

?vl(n)?ve(n),其中*为任意后继事件； ?

?vl(i)?min{vl(*)?a(i,*)}

(c) 计算vl(i)：

(d) 计算e(i,j)和l(i,j)：

e(i,j)?ve(i), l(i,j)?vl(j)?a(i,j)

(e) 结论：工程总用时ve(n)，关键活动是e(i,j)=l(i,j)的活动a(i,j)。 说明：

1. 若只求工程的总用时只要进行步骤(a)-(b)即可求得。 0

2. 如何理解计算ve(j)和vl(i)的公式：

事件j在所有前驱活动都完成后发生，所以其最早发生时间ve(j) = max{ve(*)+a(*,j)}，即取决于

最慢的前驱活动。另一方面，事件i发生后所有后继活动都可以开始了，所以其最晚发生时间vl(i) = min{vl(*)-a(i,*)}，即不耽误最慢的后继活动。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-21.html