一、最小生成树

1.最小生成树的基本概念

最小生成树：边的权值总和最小的生成树。最小生成树有很多重要的应用。《计算机学科专业基础综合辅导讲义》中就介绍了最小生成树在城市建设中的应用。

2.最小生成树的性质 最小生成树性质：设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中一条“一个端点在U中(例如：u∈U)，另一个端点不在U中的边(例如：v∈V-U)，且(u，v)具有最小权值，则一定存在G的一棵最小生成树包括此边(u，v)。

3.构造最小生成树的算法

目前已有不少构造最小生成树的算法，建议大家重点复习两种常用的构造最小生成树的算法：普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。

二、 最短路径

最短路径问题是与日常生活密切相关的问题，例如：路线选择、计算机网络路由选择等，同时也是考试重点之一。《计算机学科专业基础综合辅导讲义》分两种情况讨论了最短路径问题。

最短路径算法：

1.Dijkstra算法

Dijkstra算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

定义G=(V,E)，定义集合S存放已经找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点，即有T=V-S ：

Dijkstra算法描述如下：

(1)假设用带权的邻接矩阵edges来表示带权有向图，edges[i][j]表示弧上的权值。若不存在则置edges[i][j]=∞(计算机上用一个允许的最大值代替)。S为已经找到的从Vs出发的最短路径的终点集合，它初始化为空集。那么，从Vs出发到图上其余各顶点(终点)Vi可能达到的最短路径长度的初值为：D[i]=deges[s][i] Vi∈V

(2)选择Vj，使得D[j]=Min{D[i]|Vi∈V-S}，Vj就是当前求得的一条从Vs出发的最短路径的终点。令S=S∪{Vj}

(3)修改从Vs出发到集合V-S上任一顶点Vk可达的最短路径长度。如果D[j]+edges[j][k]

重复操作(2)(3)共n-1次。由此求得从Vs到图上其余各顶点的最短路径。

2.Floyd算法

Floyd算法的核心思想是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。

建议大家重点掌握这两种最短路径算法，并多做习题来巩固。《计算机学科专业基础综合辅导讲义同步练习》中一道娱乐中心选址问题就是应用Floyd算法来求解的。

三、 拓扑排序

1.拓扑排序基本概念

AOV网是一种可以形象地反映出整个工程中各个活动之间前后关系的有向图。在AOV网中，若不存在回路，则所有活动可排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，那么该序列为拓扑序列。

2.拓扑排序特点：

(1)拓扑序列不是唯一的。

(2)AOV网不一定都有拓扑序列。在AOV网中如果出现了有向环，则意味着某项活动应以自己作为先决条件，这是不对的，工程将无法进行。

大家要注意拓扑排序的应用，例如：利用拓扑排序判断一个图中是否存在回路。

四、 关键路径

若在带权的有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销(如该活动所需的时间)，则称此带权的有向图为AOE网。

AOE网中，从开始顶点到结束顶点之间路径长度中的最大路径为关键路径。由于AOE网中某些子工程(活动)可以同时进行，要保证每个子工程都能完成，完成该工程的最少时间就是该工程AOE网的关键路径长度。

这部分要求大家能够求解关键路径，同步练习和《计算机学科专业基础综合考试全真模拟试题集》都配有相应的练习题。

相关Tags:练习题