最近在跟同事们聊到图论的最小生成树问题，以及如何编写算法，用于工程中解决实际问题，这里我也就顺便简单写几句。
什么是最小生成树？
现在假设有一个很实际的问题：我们要在n个城市中建立一个通信网络，则连通这n个城市需要布置n-1条通信线路，这个时候我们需要考虑如何在成本最低的情况下建立这个通信网？
于是我们就可以引入连通图来解决我们遇到的问题，n个城市就是图上的n个顶点，然后，边表示两个城市的通信线路，每条边上的权重就是我们搭建这条线路所需要的成本，所以现在我们有n个顶点的连通网可以建立不同的生成树，每一颗生成树都可以作为一个通信网，当我们构造这个连通网所花的成本最小时，搭建该连通网的生成树，就称为最小生成树。
普里姆算法
构造最小生成树有很多算法，但是他们都是利用了最小生成树的同一种性质：MST性质（假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集，如果（u，v）是一条具有最小权值的边，其中u属于U，v属于V-U，则必定存在一颗包含边（u，v）的最小生成树），下面就介绍使用MST性质生成最小生成树的算法：普里姆算法。
算法思路：首先从图中的一个起点a开始，把a加入U集合，然后，寻找从与a有关联的边中，权重最小的那条边并且该边的终点b在顶点集合：（V-U）中，我们也把b加入到集合U中，并且输出边（a，b）的信息，这样我们的集合U就有：{a,b}，然后，我们寻找与a关联和b关联的边中，权重最小的那条边并且该边的终点在集合：（V-U）中，我们把c加入到集合U中，并且输出对应的那条边的信息，这样我们的集合U就有：{a,b,c}这三个元素了，一次类推，直到所有顶点都加入到了集合U。
例如存在下面的连通图：
image.png
假如我们先选择V0做为开始顶点，如上图所示，与V0直接相连的有V1、V5、V6，其中V6的权重最小，我们选择所V6加入到生成树集合中。接下来观察V0和V6，继续寻找一条到其他顶点的权重最小的边，可以看到V6->V1的权重最小，把V1加入到生成树中。以此类推，直到所有顶点完成选择。
一个C++算法实现
拿前面的图做为例子，具体实现下面的代码：
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string>
#include <vector>
#include <set>
#include <map>
// 邻边
struct SEdge
{
std::string strVertexFrom;
std::string strVertexTo;
int nEdgeWeight;
SEdge(const std::string& strFrom = "", const std::string& strTo = "", int nWeight = 0)
{
strVertexFrom = strFrom;
strVertexTo = strTo;
nEdgeWeight = nWeight;
}
};
// 邻接矩阵
class CThroughMatrix
{
// 顶点集合
std::set<std::string> m_setVertex;
// 邻边集合
typedef std::map<std::string, int> MAP_TOVERTEX_WEIGHT_t;
std::map<std::string, MAP_TOVERTEX_WEIGHT_t> m_mapEdge;
public:
CThroughMatrix()
{
}
~CThroughMatrix()
{
}
// 新增顶点名称
void addVertex(const std::string& strVertex)
{
if (m_setVertex.find(strVertex) == m_setVertex.end())
{
m_setVertex.insert(strVertex);
printf("add vertex:[%s] \n", strVertex.c_str());
}
}
// 移除指定顶点
void delVertex(const std::string& strVertex)
{
if (m_setVertex.find(strVertex) == m_setVertex.end())
return;
// 找该顶点的入度，删除邻边
for (auto iter = m_mapEdge.begin(); iter != m_mapEdge.end(); ++iter)
{
MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = iter->second;
auto iterEdge = mapToVertexWeight.find(strVertex);
if (iterEdge != mapToVertexWeight.end())
{
printf("delete edge:[%s -> %s] weight:[%d] \n", iter->first.c_str(), iterEdge->first.c_str(), iterEdge->second);
mapToVertexWeight.erase(iterEdge);
if (mapToVertexWeight.empty())
{
m_mapEdge.erase(iter);
}
}
}
// 找该顶点的出度，删除邻边
auto iter = m_mapEdge.find(strVertex);
if (iter != m_mapEdge.end())
{
MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = iter->second;
for (auto iterEdge = mapToVertexWeight.begin(); iterEdge != mapToVertexWeight.end(); ++iterEdge)
{
printf("delete edge:[%s -> %s] weight:[%d] \n", iter->first.c_str(), iterEdge->first.c_str(), iterEdge->second);
}
m_mapEdge.erase(iter);
}
// 删除顶点
m_setVertex.erase(strVertex);
}
// 增加邻边
void addEdge(const std::string& strVertex1, const std::string& strVertex2, int nWeight)
{
// 检查顶点是否存在
if (m_setVertex.find(strVertex1) == m_setVertex.end())
return;
if (m_setVertex.find(strVertex2) == m_setVertex.end())
return;
// 添加 strVertex1 -> strVertex2
{
MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = m_mapEdge[strVertex1];
auto iterEdge = mapToVertexWeight.find(strVertex2);
if (iterEdge != mapToVertexWeight.end())
{
iterEdge->second = nWeight;
printf("update edge:[%s -> %s] weight:[%d] \n", strVertex1.c_str(), strVertex2.c_str(), nWeight);
}
else
{
mapToVertexWeight.insert( std::make_pair(strVertex2, nWeight) );
printf("add edge:[%s -> %s] weight:[%d] \n", strVertex1.c_str(), strVertex2.c_str(), nWeight);
}
}
// 添加 strVertex2 -> strVertex1
{
MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = m_mapEdge[strVertex2];
auto iterEdge = mapToVertexWeight.find(strVertex1);
if (iterEdge != mapToVertexWeight.end())
{
iterEdge->second = nWeight;
printf("update edge:[%s -> %s] weight:[%d] \n", strVertex2.c_str(), strVertex1.c_str(), nWeight);
}
else
{
mapToVertexWeight.insert( std::make_pair(strVertex1, nWeight) );
printf("add edge:[%s -> %s] weight:[%d] \n", strVertex2.c_str(), strVertex1.c_str(), nWeight);
}
}
}
// 删除邻边
void delEdge(const std::string& strVertex1, const std::string& strVertex2)
{
// 检查顶点是否存在
if (m_setVertex.find(strVertex1) == m_setVertex.end())
return;
if (m_setVertex.find(strVertex2) == m_setVertex.end())
return;
// 删除 strVertex1 -> strVertex2
{
auto iter = m_mapEdge.find(strVertex1);
if (iter != m_mapEdge.end())
{
MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = iter->second;
auto iterEdge = mapToVertexWeight.find(strVertex2);
if (iterEdge != mapToVertexWeight.end())
{
mapToVertexWeight.erase(iterEdge);
if (mapToVertexWeight.empty())
{
m_mapEdge.erase(strVertex1);
}
printf("delete edge:[%s -> %s] \n", strVertex1.c_str(), strVertex2.c_str());
}
}
}
// 删除 strVertex2 -> strVertex1
{
auto iter = m_mapEdge.find(strVertex2);
if (iter != m_mapEdge.end())
{
MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = iter->second;
auto iterEdge = mapToVertexWeight.find(strVertex1);
if (iterEdge != mapToVertexWeight.end())
{
mapToVertexWeight.erase(iterEdge);
if (mapToVertexWeight.empty())
{
m_mapEdge.erase(strVertex1);
}
printf("delete edge:[%s -> %s] \n", strVertex2.c_str(), strVertex1.c_str());
}
}
}
}
// 计算最小生成树
void calcMinWeightTreeByPrim(std::vector<SEdge>& vecEdge) const
{
std::set<std::string> setVertexLeft, setVertexRight = m_setVertex;
if (setVertexRight.empty())
{
printf("no vertex! \n");
return;
}
// 初使合左右顶点集合
const std::string& strVertex = *setVertexRight.begin();
setVertexLeft.insert(strVertex);
setVertexRight.erase(strVertex);
while (!setVertexRight.empty())
{
// 寻找从左边顶点到右边顶点的最小邻边
std::string strFrom = "", strTo = "";
int nMinWeight = -1;
for (auto iterLeft = setVertexLeft.begin(); iterLeft != setVertexLeft.end(); ++iterLeft)
{
const std::string& strLeft = (*iterLeft);
auto iter = m_mapEdge.find(strLeft);
if (iter == m_mapEdge.end())
{
printf("vertex:[%s] no edge! \n", strLeft.c_str());
return;
}
const MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = iter->second;
for (auto iterEdge = mapToVertexWeight.begin(); iterEdge != mapToVertexWeight.end(); ++iterEdge)
{
const std::string& strRight = iterEdge->first;
// 只检查到右边顶点的边
if (setVertexRight.find(strRight) == setVertexRight.end())
continue;
if (nMinWeight < 0 || iterEdge->second < nMinWeight)
{
strFrom = strLeft;
strTo = strRight;
nMinWeight = iterEdge->second;
}
}
}
if (strTo != "")
{
SEdge stEdge(strFrom, strTo, nMinWeight);
vecEdge.push_back(stEdge);
setVertexLeft.insert(strTo);
setVertexRight.erase(strTo);
}
}
}
};
int main(int argc, char* argv[])
{
CThroughMatrix throughMatrix;
throughMatrix.addVertex("V0");
throughMatrix.addVertex("V1");
throughMatrix.addVertex("V2");
throughMatrix.addVertex("V3");
throughMatrix.addVertex("V4");
throughMatrix.addVertex("V5");
throughMatrix.addVertex("V6");
throughMatrix.addEdge("V0", "V1", 4);
throughMatrix.addEdge("V0", "V5", 5);
throughMatrix.addEdge("V0", "V6", 2);
throughMatrix.addEdge("V1", "V0", 4);
throughMatrix.addEdge("V1", "V2", 2);
throughMatrix.addEdge("V1", "V6", 1);
throughMatrix.addEdge("V2", "V1", 2);
throughMatrix.addEdge("V2", "V3", 10);
throughMatrix.addEdge("V2", "V6", 3);
throughMatrix.addEdge("V3", "V2", 10);
throughMatrix.addEdge("V3", "V4", 6);
throughMatrix.addEdge("V3", "V6", 7);
throughMatrix.addEdge("V4", "V3", 6);
throughMatrix.addEdge("V4", "V5", 1);
throughMatrix.addEdge("V4", "V6", 4);
throughMatrix.addEdge("V5", "V0", 5);
throughMatrix.addEdge("V5", "V4", 1);
throughMatrix.addEdge("V5", "V6", 8);
throughMatrix.addEdge("V6", "V0", 2);
throughMatrix.addEdge("V6", "V1", 1);
throughMatrix.addEdge("V6", "V2", 3);
throughMatrix.addEdge("V6", "V3", 7);
throughMatrix.addEdge("V6", "V4", 4);
throughMatrix.addEdge("V6", "V5", 8);
std::vector<SEdge> vecEdge;
throughMatrix.calcMinWeightTreeByPrim(vecEdge);
for (auto iterEdge = vecEdge.begin(); iterEdge != vecEdge.end(); ++iterEdge)
{
SEdge& stEdge = (*iterEdge);
printf("edge[%s -> %s] weight:[%d] \n", stEdge.strVertexFrom.c_str(), stEdge.strVertexTo.c_str(), stEdge.nEdgeWeight);
}
return 0;
}
编译：
g++ -o testprim testprim.cpp -std=c++11
运行结果如下：
add vertex:[V0]
add vertex:[V1]
add vertex:[V2]
add vertex:[V3]
add vertex:[V4]
add vertex:[V5]
add vertex:[V6]
add edge:[V0 -> V1] weight:[4]
add edge:[V1 -> V0] weight:[4]
add edge:[V0 -> V5] weight:[5]
add edge:[V5 -> V0] weight:[5]
add edge:[V0 -> V6] weight:[2]
add edge:[V6 -> V0] weight:[2]
update edge:[V1 -> V0] weight:[4]
update edge:[V0 -> V1] weight:[4]
add edge:[V1 -> V2] weight:[2]
add edge:[V2 -> V1] weight:[2]
add edge:[V1 -> V6] weight:[1]
add edge:[V6 -> V1] weight:[1]
update edge:[V2 -> V1] weight:[2]
update edge:[V1 -> V2] weight:[2]
add edge:[V2 -> V3] weight:[10]
add edge:[V3 -> V2] weight:[10]
add edge:[V2 -> V6] weight:[3]
add edge:[V6 -> V2] weight:[3]
update edge:[V3 -> V2] weight:[10]
update edge:[V2 -> V3] weight:[10]
add edge:[V3 -> V4] weight:[6]
add edge:[V4 -> V3] weight:[6]
add edge:[V3 -> V6] weight:[7]
add edge:[V6 -> V3] weight:[7]
update edge:[V4 -> V3] weight:[6]
update edge:[V3 -> V4] weight:[6]
add edge:[V4 -> V5] weight:[1]
add edge:[V5 -> V4] weight:[1]
add edge:[V4 -> V6] weight:[4]
add edge:[V6 -> V4] weight:[4]
update edge:[V5 -> V0] weight:[5]
update edge:[V0 -> V5] weight:[5]
update edge:[V5 -> V4] weight:[1]
update edge:[V4 -> V5] weight:[1]
add edge:[V5 -> V6] weight:[8]
add edge:[V6 -> V5] weight:[8]
update edge:[V6 -> V0] weight:[2]
update edge:[V0 -> V6] weight:[2]
update edge:[V6 -> V1] weight:[1]
update edge:[V1 -> V6] weight:[1]
update edge:[V6 -> V2] weight:[3]
update edge:[V2 -> V6] weight:[3]
update edge:[V6 -> V3] weight:[7]
update edge:[V3 -> V6] weight:[7]
update edge:[V6 -> V4] weight:[4]
update edge:[V4 -> V6] weight:[4]
update edge:[V6 -> V5] weight:[8]
update edge:[V5 -> V6] weight:[8]
edge[V0 -> V6] weight:[2]
edge[V6 -> V1] weight:[1]
edge[V1 -> V2] weight:[2]
edge[V6 -> V4] weight:[4]
edge[V4 -> V5] weight:[1]
edge[V4 -> V3] weight:[6]
可以看到最小生成树的生成过程为：
edge[V0 -> V6] weight:[2]
edge[V6 -> V1] weight:[1]
edge[V1 -> V2] weight:[2]
edge[V6 -> V4] weight:[4]
edge[V4 -> V5] weight:[1]
edge[V4 -> V3] weight:[6]
即如下的图：
image.png
