如何从 networkx 图中的每个节点删除最小权重边

Question

我有一个无向图，我正在寻找一种方法来从每个节点中删除最小权重边。我尝试了几种方法，但它们似乎都失败了。

Answer 1

首先创建一个具有随机权重的完整图：

g = nx.complete_graph(5)
for (u,v,w) in g.edges(data=True):
    w['weight'] = random.randint(0,10)

选项 1：遍历节点并删除最小权重边。

for n in g.nodes():
    min_weight = (-1,-1,float("inf"))
    for e in g.edges(nbunch=n,data="weight"):
        #print(e)
        if min_weight[2] > e[2]:
            min_weight = e
    print(min_weight)
    g.remove_edge(min_weight[0], min_weight[1])

方案二：最后去掉边。

只在最后删除边，检查该边是否已经在要删除的边列表中。

edges_to_remove = set()
for n in g.nodes():
    min_weight = (-1,-1,float("inf"))
    for e in g.edges(nbunch=n,data="weight"):
        #print(e)
        if min_weight[2] > e[2]:
            min_weight = e
    
    if (min_weight[1],min_weight[0]) not in edges_to_remove:
        print(min_weight)
        edges_to_remove.add((min_weight[0],min_weight[1]))

for e in edges_to_remove:
    g.remove_edge(*e)

请注意，这两个解决方案会产生不同的结果：

对于同一张图：

边 (u,v,weight) 使用选项 1 移除：

(0, 3, 3)
(1, 2, 0)
(2, 3, 7)
(3, 1, 8)
(4, 1, 3)

边缘 (u,v,weight) 使用选项 2 移除：

(0, 3, 3)
(1, 2, 0)
(4, 1, 3)

第一个选项根据顺序移除每个节点的最小权重边！，即如果最小权重边已经被移除，它将移除下一个最小权重边.将始终删除与节点数一样多的边。
第二个选项只移除每个节点的最小权重边，即如果给定节点的最小边已经被移除，它不会移除任何边。

Answer 2

给定一个完整的图

>>> G = nx.complete_graph(n=5)
>>> for (u, v) in G.edges():
...     G.edges[u,v]['weight'] = random.randint(0,10)

要获取节点的最小权重边，然后将其删除，您可以执行以下操作。

>>> for u in G.nodes():
...     min_weight_edge = min(G.edges(u), key=lambda x: G.get_edge_data(x[0], x[1])["weight"])
...     G.remove_edge(*min_weight_edge)
...

如何从 networkx 图中的每个节点删除最小权重边

How to remove minimum weight edge from each node in a networkx graph

networkx

python-3.x

选项 1：遍历节点并删除最小权重边。

方案二：最后去掉边。