2018-2-2-KMP.md

layout	post
title	最小生成树算法介绍
categories	Algorithms
description
keywords

定义

最小生成树其实是最小权重生成树的简称。一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或Prim（普里姆）算法求出。最小生成树性质：设G=(V，E）是一个连通网络，U是顶点集V的一个非空真子集。根据树的定义，则T中必有一条从红点u到蓝点v的路径P，且P上必有一条紫边（u'，v'）连接红点集和蓝点集，否则u和v不连通。当一条边（u，v）加入T时，必须保证T∪(u，v)仍是MST的子集，我们将这样的边称为T的安全边。

两种最小生成树算法

Prim算法

此算法可以用一句话总结：距离已选中的所有点最近的点被选中。

算法描述：从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。

    输入：一个加权连通图，其中顶点集合为V，边集合为E  
    输出：使用集合Vnew和Enew来描述所得到的最小生成树  
      
    算法流程：  
      
      1.初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {}；  
      
      2.重复下列操作，直到Vnew = V:  
	<1>在集合E中选取权值最小的边（u, v），其中u为集合Vnew中的元素，而v则是V中没有加入Vnew的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；  
	<2>将v加入集合Vnew中，将（u, v）加入集合Enew中；

下面给出一个无向图，每条边上的数字为权值：