rustworkx.minimum_spanning_edges

minimum_spanning_edges(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]
>>> rx.minimum_spanning_edges(G, weight_fn=lambda x: x)
WeightedEdgeList[(2, 3, 4), (0, 3, 5), (0, 1, 10)]

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

要获取图结果，请参见minimum_spanning_tree()。

Parameters:

• graph (PyGraph) – 一个无向图

• weight_fn –

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

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

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

  rx.minimum_spanning_edges(G, weight_fn=float)

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

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

Returns:

\(N - |c|\) 条最小生成树（或森林，如果 \(|c| > 1\)）的边，此处 \(N\) 代表节点数量，\(|c|\) 代表图的连通分量数量。

Return type:

WeightedEdgeList

Raises:

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