rustworkx.minimum_spanning_tree#

minimum_spanning_tree(graph, weight_fn=None, default_weight=1.0)#

使用Kruskal算法寻找无向图的最小生成树或森林。

最小生成树（MST）是一个连通无向图的边子集，它连接所有顶点且无环，并具有最小的总边权重。

该函数计算构成无向图的最小生成树（MST）或森林的边。Kruskal算法通过对图中所有边按权重进行排序，然后逐一添加到MST中，同时确保不形成环。

>>> G = rx.PyGraph()
>>> G.add_nodes_from(["A", "B", "C", "D"])
NodeIndices[0, 1, 2, 3]
>>> G.add_edges_from([(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)])
EdgeIndices[0, 1, 2, 3, 4]
>>> mst_G = rx.minimum_spanning_tree(G, weight_fn=lambda x: x)
>>> mst_G.weighted_edge_list()
WeightedEdgeList[(2, 3, 4), (0, 3, 5), (0, 1, 10)]

在这个例子中，边 (0, 2, 6) 不会成为最小生成树（MST）的一部分，因为在考虑该边时，由于权重更低，连接节点 0-3-2 的另外两条边已经是 MST 的组成部分。

如需获取仅作为边列表的结果，请查看minimum_spanning_edges()。

Parameters:

  • graph (PyGraph) – 一个无向图

  • weight_fn –

    一个可调用对象（函数、lambda表达式等），它接受一个边对象并返回一个float。此函数用于提取各边的数值权重。例如：

    rx.minimum_spanning_tree(G, weight_fn=lambda x: 1)

    将为所有边分配权重1，从而忽略实际权重。

    rx.minimum_spanning_tree(G, weight_fn=float)

    将直接将边对象转换为float以确定其权重。

  • default_weight (float) – 如果未指定 weight_fn，那么这个可选的浮点数值将被用作每条边的权重/成本。

Returns:

一个最小生成树（如果图为非连通图，则为森林）。

Return type:

PyGraph

注意

新图将保持相同的节点索引，但边索引可能有所不同。

Raises:

ValueError – If a NaN value is found (or computed) as an edge weight.