天津大学本科课程考研数据结构全.ppt

* nearvex[u] = -1; //加到生成树顶点集合 int k = 0; //存放最小生成树结点的变量 for ( i = 0; i G.n; i++ ) if ( i != u ) { //循环n-1次, 加入n-1条边 EdgeData min = MaxValue; int v = 0; for ( int j = 0; j NumVertices; j++ ) if ( nearvex[j] != -1 // =-1不参选 lowcost[j] min ) { v = j; min = lowcost[j]; } //求生成树外顶点到生成树内顶点具有最 //小权值的边, v是当前具最小权值的边 * if ( v ) { //v=0表示再也找不到要求顶点 T[k].tail = nearvex[v]; //选边加入生成树 T[k].head = v; T[k++].cost = lowcost[v]; nearvex[v] = -1; //该边加入生成树标记 for ( j = 0; j G.n; j++ ) if ( nearvex[j] != -1 G.Edge[v][j] lowcost[j] ) { lowcost[j] = G.Edge[v][j]; //修改 nearvex[j] = v; } } * } //循环n-1次, 加入n-1条边 } 分析以上算法, 设连通网络有 n 个顶点, 则该算法的时间复杂度为 O(n2), 它适用于边稠密的网络。 注意：当各边有相同权值时，由于选择的随意性，产生的生成树可能不唯一。当各边的权值不相同时，产生的生成树是唯一的。 * 活动网络 (Activity Network) 计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。 例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。 用顶点表示活动的网络 (AOV网络) * C1 高等数学 C2 程序设计基础 C3 离散数学 C1, C2 C4 数据结构 C3, C2 C5 高级语言程序设计 C2 C6 编译方法 C5, C4 C7 操作系统 C4, C9 C8 普通物理 C1 C9 计算机原理 C8 课程代号 课程名称 先修课程 * 学生课程学习工程图 C8 C3 C5 C4 C9 C6 C7 C1 C2 * 可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边Vi, Vj表示活动Vi 必须先于活动Vj 进行。这种有向图叫做顶点表示活动的AOV网络 (Activity On Vertices)。 在AOV网络中不能出现有向回路, 即有向环。如果出现了有向环，则意味着某项活动应以自己作为