精心整理1.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树
1.1问题背景：
假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。在每两个
1.2
个顶
图
G5
G5的三棵生成树：
可以证明，对于有n个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1条边。
1.3最小生成树的定义：
如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。
最小生成树的性质：
假设N=(V,{E})是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中，
则必存在一棵包含边（u,v）的最小生成树。
1.4解决方案：
两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。他们都利用了最小生成树的性质
1.普里姆（Prim）算法：有线到点，适合边稠密。时间复杂度O(N^2)
假设G＝（V，E）为连通图，其中V为网图中所有顶点的集合，E为网图中所有带权边的集合。设置两个新的集合U和T，其中
集合U（顶点集）用于存放G的最小生成树中的顶点，
集合T（边集合）存放G的最小生成树中的边。
T，U的初始状态：令集合U的初值为U＝{u1}（假设构造最小生成树时，从顶点u1出发），集合T的初值为T＝{}。
Prim算法的思想是：从所有u∈U，v∈V－U的边中，选取具有最小权值的边（u，v）∈E，将顶点v加入集合U中，将边（u，v）加入集合T中，如此不断重复，直到U ＝V时，最小生成树构造完毕，这时集合T中包含了最小生成树的所有边。
Prim算法可用下述过程描述，其中用wuv表示顶点u与顶点v边上的权值。
（1
（2
(u，
T＝T
U＝U
（3
按照
typedefstructArcNode
{
intadjvex;//adjex域存储该边依附的在U中的顶点
VrTypelowcost;//lowcost域存储该边上的权重
}closedge[MAX_VERTEX_NUM];
显然：
初始状态时，U＝{v1}(u1为出发的顶点),则到V-U中各项中最小的边，即依附顶点v1的各条边中，找到一条代价最小的边（u0，v0）=（1，3）为生成树上一条边。同时将v0（=v3）并入集合U中。然后修改辅助数组的值。
1）将closedge[2].lowcost=0；//表示顶点V3三已经并入U
2)由于边（v2,v3）的权值小于closedge[1].lowcost，故需修改closedge[1]为边（v2,v3）及其权值，同理修改closedge[4]，closedge[5].
closedge[1].adjvex=3.
closedge[1].lowcost=5.
closedge[4].adjvex=1.
closedge[4].lowcost=5.
closedge[5].adjvex=3.
closedge[5].lowcost=6.
以此类推，直至U=V;
下图给出了在用上述算法构造网图7.16的最小生成树的过程中：Prim算法实现：
按照算法框架:
（1）U＝{u1},T={};
频度为n-1；其二是重新选择具有最小代价的边，其频度为n。由此，普里姆算法的时间复杂度为O(n2)，与网中的边数无关，因此适用于求边稠密的网的最小生成树。
2.克鲁斯卡尔（Kruskal）:由点到线，适合边稀疏的网。时间复杂度：O(e*loge)
Kruskal算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。
基本思想是：
1)设无向连通网为G＝（V，E），令G的最小生成树为T，其初态为T＝（V，{}），即开始时，最小生成树T由图G中的n个顶点构成，顶点之间没有一条边，这样T
2)在
1按照
算法的框架：
构造非连通图T＝（V，{}）
k=i=0；//k为边数
while（k《i++;
检查边E中第i条边的权值最小边（u，v）
AOV网
称顶点j是顶点i的后继。若是图中的弧，则称顶点i是顶点j的直接前驱，顶点j是顶点i的直接后驱。
AOV网中的弧表示了活动之间存在的制约关系。例如，计算机专业的学生必须完成一
系列规定的基础课和专业课才能毕业。学生按照怎样的顺序来学习这些课程呢？这
个问题可以被看成是一个大的工程，其活动就是学习每一门课程。这些课程的名称与相应代号如表所示。
课程之间的优先关系图：
在
该
2.2
若集合A中的二元关系R是自反的、非对称的和传递的，则R是A上的偏序关系。集合A与关系R一起称为一个偏序集合。
若R是集合A上的一个偏序关系，如果对每个a、b∈A必有aRb或bRa，则R是A上的全序关系。集合A与关系R一起称为一个全序集合。
直观地看，偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较。
[例如]，图7.25所示的两个有向图，图中弧(x,y)表示x≤y，则(a)表示偏序，(b)表示全序。若在(a)的有向图上人为地加一个表示v2≤v3的弧(符号“≤”表示v2
领先于v3)，则(a)表示的亦为全序，且这个全序称为拓扑有序(TopologicalOrder)，
2.3
对
1
2
3
以下图(a)中的有向图为例，图中v1，和v6没有前驱，则可任选一个。假设先输出v6,在删除v6及弧，之后，只有顶点v1没有前驱，则输出vl且删去vl及弧、和，之后v3和v4都没有前驱。依次类推，可从中任选一个继续进行。最后得到该有向图的拓扑有序序列为：
