最小生成树and最短路径.doc

最小生成树and最短路径
无独有偶，在两个学期的期末中两门不同的科目《离散数学》和《数据结构》中都谈到了图及其衍生的最小生成树、最短路径问题，并给出了相应的算法——克鲁斯卡尔、普林、迪杰斯特拉、沃舍尔算法。这无疑是释放了一个很大的信号——这些内容很重要。由于之前学《离散数学》时只要求在思想上理解，并没要求程序实现，所以学起来也挺吃力的。而现在来到了《数据结构》的课程上，我觉得还是有必要写写理解与体会，好让以后用起来没那么难。

最小生成树（Minimum Spanning Tree,MST ）
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。即是在原图上删除边，直到剩余n-1条边，保证n个结点连通且边的权值加起来最小。

简单图示：

2
1
1
2
1
1
3 2 MST
2
5
4
3
4
3

4 4

克鲁斯卡尔（Kruskal）算法
克鲁斯卡尔算法从边的角度来解决问题，即在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。然而，图的存贮结构采用边集数组，且权值相等的边在数组中排列次序可以是任意的，该方法对于边数相对比较多的图不是很实用，浪费时间。可以说克鲁斯卡尔算法是很直观的算法，适合人的直观思考方式，但是因为上面论述的缘故，克鲁斯卡尔算法比较适用在稀疏图（边的数目不是很多的图）上。

边集数组：
从图变为程序需要的数据，需要采用合适的数据结构。由算法的核心思想上看，我们需要存储的数据为边，而边的要素包括三点：连接的两个结点、边的权值。然而边并不需要具有什么操作来改变自身或者做些什么，所以用struct来自定义就合适不过了。

struct edge{
int node_1;
int node_2;
int value ;
};
另外，文中提及了最小边、次小边，这就暗示了应该对所有的边进行排序（sort）。
比较函数应以value作衡量。

bool cmp(edge a , edge b)
{
    return a.value < b.value ;
}

现在剩余最后的问题——回路的避免。其实这个也很容易避免，我们可以定义一个数组used[max]，它记录了每一个结点是否被应用的情况，当要加入的一条边中used[a.node_1]和
used[a.node_2]都已被应用，那么加入的这条边必然造成回路，否则不会。若造成回路，则舍弃这条边，转而观察加入次小边。

排序后的情况
edge数组

node_1
node_2
value
0
1
2
1
1
2
4
2
2
2
4
3
3
3
4
4
4
2
3
5

用红线将舍弃的边删除后，剩余的就成为了最小生成树了。

时间复杂度
若e表示图的边数，那么，排序过程将有O(eloge)，生成过程则是O(e)，故总的来说，时间复杂度为O(eloge)。

普林（Prim）算法
克鲁斯卡尔算法以边为出发点，相应地，普林算法则以点为出发点。从指定顶点开始将它加入集合中，然后将集合内的顶点与集合外的顶点所构成的所有边中选取权值最小的一条边作为生成树的边，并将集合外的那个顶点加入到集合中，表示该顶点已连通。再用集合内的顶点与集合外的顶点构成的边中找最小的边，并将相应的顶点加入集合中。如此下去直到全部顶点都加入到集合中，即得最小生成树。以点作为出发点很好地解决了克鲁斯卡尔算法解决边数很多的图的可怕时间复杂度的问题。边数不是制约普林算法的因素，结点才是。

普林算法的简单演算步骤：
（1）初始化集合A()，表示没有点以加入到生成结点中，初始化集合B，使B包含所有结点；
（2）从B中选择一个点作为始加入到A中并从B中剔除；
（3）选择A中所有的点中能到达B的最小权值边，将这条边的另一个点加入到A中并从B中剔除；
（4）重复（3）操作直至B为NULL，则为最小生成树。

邻接矩阵
如果说克鲁斯卡尔算法使用自定义的边集数组存储图是直观的，那么普林算法采用自定义的点集数组也是合适的？如果以某一点作为单独的数据结构，那么这一数据结构应当包含有与这个点有关的边的所有信息——权值和对应点。但事前我们并不知道这个图的点的最大度数为多少，带着这种未知来定义struct是危险的，所以我们应当采用邻接矩阵——一个存放顶点间关系（边或弧）的数据的二维矩阵，即有一个二维矩阵data，data[a][b]=c表示a结点和b结点有一条长为c的边，相应地，data[b][a]=c。当a,b之间没有边的时候，应当使data[a][b] = INF（INF表示无穷）。

集合
由演算步骤中得知我们需要抽象出一个集合的概念，用以分开集合A和集合B。对于这种简单的区分，大可不必抽象出对象出来。运用克鲁斯卡尔中used数组的概念也可模拟出这种集合，当used[i]等于特定值代表结点i在哪个集合中即可。

初始化used状态（等于0代表在B中）

memset(used,0,sizeof(used));

然后选取第一结点来实现（2）操作

used[0] = 1 ;

优化（3）
（3） 选择A中所有的点中能到达B的最小权值边，将这条边的另一个点加入到A中并从B中剔除；
如何寻找最小权值边？如果直观地去做，从A中各点遍历，那么每加入一个点到A所费的时间也是惊人的，所以也引入两个数组来作优化。
lowcost数组：lowcost[i]表示A集合中到结点i(I必然在集合B中)的权值；
closest数组：对应与lowcost，表示结点i到集合A的用最小权值边连通的点。
所以当（2）中采用了第一结点，那么这个数组应当被初始化为

for(int kn = 1; kn < n ; ++kn ){
lowcost[kn] = data[0][kn];
closest[kn] = 0 ;
}
当进行（3）时只需这样寻找

for(int i = 0 ; i < n ;++i ){
if( !used[i] && lowcost[i] < min ) {
min = lowcost[i] ;
min_site = i ;
}
}
每执行一次（3）都需要对着两个数组进行更新

for (int ks = 0 ; ks < n ; ks++){
if (!used[ks] && (data[min_site][ks] < lowcost[ks])){
owcost[ks] = data[min_site][ks];
closest[ks] = min_site ;
}
}

时间复杂度
若n表示图的结点数，那么初始化需要O(n)，找出最小边O(n)，更新为O(n)，需要找出与更新n次总的为O(n*(2n)+n)，即O(n*n)。

最短路径
最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

2
1
18
1
5
4
4

10 7 30 从1到4最短路径 10
5
3
9 9
5
3
1
1

迪杰斯特拉（Dijkstra）算法
Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解。但是，由于它遍历计算的节点很多，所以效率低。

基本思想
设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。
初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。迪杰斯特拉算法每次从所有特殊路径中取出最短特殊路径及其顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。

简单模拟
沿用克鲁斯卡尔算法used数组来模拟集合S。
初始化：结点1作为源点，此时的特殊路径有{1-2、1-3、1-4}，最短特殊路径为1-3
1

103

明显结点3到源点的最短路径已定，则结点3也在S集合中，dist[3]被赋值为10。
1
S加入结点3后，特殊路径有{1-2、1-3、1-4、1-3-2、1-3-5}，最短特殊路径为1-3-5

5
103

1

明显结点5到源点的最短路径已定，则结点5也在S集合中，dist[5]被赋值为11。
以此类推，直到所有的点的dist被计算出来。

难点
无论是边集数组还是邻接矩阵来存储图，对迪杰斯特拉算法来说影响不大，或者说各有各的优劣，视问题分析而定。由上面的分析可以看出，迪杰斯特拉算法的难点在于在特殊路径中找出最短的那条并最后将它删除。对于这种情况，其实我们可以构造一个类来存储最短特殊路径，并使它对特殊路径具有push、pop、sort等的功能。不过STL也提供了类似的类——priority_queue。

弗洛伊德沃舍尔（Warshall ）算法
沃舍尔算法只需要使用2n^3次位运算就可以求出传递闭包。

传递闭包
在数学中，在集合 X 上的二元关系 R 的传递闭包是包含 R 的 X 上的最小的传递关系。当图中点边关系以邻接矩阵给出时，利用沃舍尔算法能够在O(n^3)内算出每点到各个点的最短路径，并以邻接矩阵形式给出。

五行代码之美
如果结点i与j之间能通过介质点med来获得更短路径，则更新place[i][j]的值
共有num_pl个结点，place[i][j]表示结点i到结点j的边权值为place[i][j]，不存在边时则赋值INF标志。
for(int med = 1 ; med <= num_pl ; ++med)
for(int i = 1 ; i <= num_pl ; ++i)
for(int j = 1 ; j <= num_pl ; ++j)
if(place[i][j] > place[i][med] + place[med][j])
place[i][j] = place[i][med] + place[med][j] ;