数据结构之图论（续）

2020-04-27 16:48

NO．3最小支撑树

在上面我们介绍了关节点算法，现在我们来谈下另外一个概念，支撑树。在一个联通图G中，某一个能够连接所有点的无环子图，则称作G的一棵支撑树或生成树（spanning tree），如果边带有权值，那么生成的支撑树中所有权值最小树就是最小支撑树或者最小生成树。

聚类分析、网络架构设计、VLSI布线设计等诸多实际应用问题，都可转化并描述为最小支撑树的构造问题。在这些应用中，边的权重大多对应于某种可量化的成本，因此作为对应优化问题的基本模型，掌握最小生成树算法很重要。
这种问题，暴力是不可取的，时间复杂度太高，那么让我们一步步分析下。

我们首先假设G＝（V，E）是一个连通网络，U是顶点集V的一个非空真子集。若（u，v）是G中一条“一个端点在U中（例如：u∈U），另一个端点不在U中的边（例如：v∈V－U），且（u，v）具有最小权值，则一定存在G的一棵最小生成树包括此边（u，v），我们先假设这条边为安全边ri。

这样，我们假设我们要的树是个只包含一个点的集合即为U，另外的点为V－U，然后我们就把安全边加入进去，然后更新这两个集合的数据。依次进行下去直到所有点进入。但是这样子的时间复杂度还是有点高，我们想一下还有上面优化的方法。怎样才能减少每次更新的时间呢？我们还有一个强大的助手STL。

STL中的优先队列提供了快捷的插入和修改，可以极大地优化时间。

下为示例与优化后的代码：

a＞首先选择A结点作为点集

b＞找A－－B，A－－D，A－－G权值最小的点（B），之后将其加入点集中

c＞找点集中跨越边最小的边，A－－D，A－－G，B－－C，到D的权值最小，将其加入到点集中

d＞重复上述过程，A－－G，D－－G，D－－E，B－－C，到G的权值最小，将其加入到点集中

一直重复上述步骤直到找到的边数为n－1条，i就是通过Prim算法找到的最小生成树了。

声明： 本文由入驻维科号的作者撰写，观点仅代表作者本人，不代表OFweek立场。如有侵权或其他问题，请联系举报。

共0条评论，0人参与

登录登录即可访问所有OFweek服务

请输入评论内容...

请输入评论/评论长度6~500个字

暂无评论

图片新闻

技术文库

行业报告