算法导论 23.2 Kruskal算法

一，Kruskal算法的思想

        Kruskal算法对最小生成树安全边的通用确定规则进行了细化，在该算法中，集合A是一个森林，其结点就是给定图的结点，每次加入到集合A中的安全边永远是权重最小的连接两个不同分量的边。

二，Kruskal算法介绍

        准备阶段：一个赋值无向连通图G=(V,E)，我们需要一个集合A用于存放加入的安全边，最后A中的边形成最小生成树

        算法过程：在所有连接森林中两棵不同树的边中，找到权重最小的边(u,v)，由于这条边连接了两棵树，因此他一定横跨某个切割，再加上是权重最小的边，所以满足安全边的辨别定理。

三，Kruskal算法伪代码

MST_KRUSKAL(G,w)

1. A=∅

2. for each vertex v∈G.V

3.     MAKE_SET(v)

4. sort the edges of G.E into nondecreasing order by weight w

5. for each edge(u,v)∈G.E,taken in nondecreasing order by weight

6.     if FIND_SET(u)≠FIND_SET(v)

7.         A=A∪{(u,v)}

8.         UNION(u,v)

9. return A

第1行中，引入集合A并设为空集；第2.3行中，MAKE_SET方法让每个结点都成为一个集合（树），每个集合都只先有一个结点；第4行中，由于我们每次要找权重最小的边，所以我们把所有边按权重升序排列；第5-8行，按照边的权重升序的次序依次取出边(u,v)，通过FIND_SET方法检查边的两端u和v是否在同一个集合（树）里，若不在一个集合（树）里，这条边就为安全边，将这条边(u,v)加入集合A中，并将u、v两个集合（树）合并；第9行返回集合A

        以书上的例子为例，图a中，我们找到权重最小的边(h,g)，由于h（集合为{h}）和g（集合为{g}）不在同一个集合里，因此将这条边加入集合A中，我们把他涂上阴影，并且将两个端点h和g合并，即h、g的集合均为{h,g}；图b-e中，我们接着找到了权重最小的4条边(c,i)、(g,f)、(a,b)、(c,f)，由于他们的端点都不在一个集合里，因此都加入集合A，涂上阴影并且合并两个端点，合并后的集合情况为：{a,b},{c,f,g,h,i}；图f中，我们继续找剩下边中权值最小的边(i,g)，由于i、g在同一个集合中，所以不加入集合A；图g到图n，依然遵循上述规律，最后涂上阴影的边即集合A，即最小生成树

四，Kruskal算法的复杂度

时间复杂度：O(ElgV)或O(ElgE)

五，Kruskal算法的代码

代码中创建了一个二维数组，第一维为各结点，第二维为各结点的集合

Tree * Kruskal_ALGO(Graph * graph)
{Tree *T = new Tree();//创建最小生成树int nodestotalnum = graph->getNodeList().size();//获取结点总数int edgestotalnum = graph->getEdgeList().size();//获取边的总数vector<vector<Node *>> nodeset(nodestotalnum);//对每个结点创建一个集合for (int i = 0; i < nodestotalnum; i++)//初始化结点集合{nodeset[i].push_back(graph->getNodeList()[i]);}vector<Edge *> unpickededge= graph->getEdgeList();//创建并初始化未被取出的边的集合for (int i = 0; i < edgestotalnum; i++)//遍历所有边{Node *u = new Node();Node *v = new Node();int minweight = 10000;int minedgeid = 100;for (int j = 0; j < unpickededge.size(); j++)//找出未被取出的边中的最小边即两个结点{if (unpickededge[j]->getWeight() < minweight){minweight = unpickededge[j]->getWeight();u = unpickededge[j]->getStartNode();v = unpickededge[j]->getEndNode();minedgeid = j;}}if (nodeset[Find_Set(nodeset, u)] != nodeset[Find_Set(nodeset, v)])//若u,v不属于同一个集合{T->pushEdge(unpickededge[minedgeid]);//加入生成树中Union_Set(nodeset, Find_Set(nodeset, u), Find_Set(nodeset, v));//合并集合的两行}unpickededge.erase(unpickededge.begin() + minedgeid);//从未被取出的边中删除该边}return T;
}

int Find_Set(vector<vector<Node *>> set,Node * u)//找到含有顶点u的顶点集合,返回所在行数
{for (int i = 0; i < set.size(); i++)//遍历行{for (int j = 0; j < set[i].size(); j++)//遍历列{if (set[i][j] == u){return i;}}}
}

void Union_Set(vector<vector<Node *>> &nodeset, int a,int b)//合并两个顶点集合（两行）
{for (int i = 0; i < nodeset[a].size(); i++){nodeset[b].push_back(nodeset[a][i]);//将a中结点添加至b中}nodeset[a] = nodeset[b];
}