python - 使用 networkx 从图中删除边

Question

我正在尝试将 DiGraph 转换为 n 叉树并按级别顺序或 BFS 显示节点。我的树与此类似，但要大得多，为简单起见，使用此示例:

G = networkx.DiGraph()
G.add_edges_from([('n', 'n1'), ('n', 'n2'), ('n', 'n3')])
G.add_edges_from([('n4', 'n41'), ('n1', 'n11'), ('n1', 'n12'), ('n1', 'n13')])
G.add_edges_from([('n2', 'n21'), ('n2', 'n22'), ('n', 'n22')])
G.add_edges_from([('n13', 'n131'), ('n22', 'n221'), ('n', 'n131'), ('n', 'n221')])

树:从这个question中借用了数据并适当修改:

n---->n1--->n11
 |     |--->n12
 |     |--->n13
 |-----------|--->n131 
 |--->n2              
 |     |---->n21     
 |     |---->n22     
 |------------|--->n221 
 |--->n3

现在我的真实数据集要复杂得多，有数百个节点，为了简单起见，我使用了上图。

我想从树中删除不必要的边，这样如果父项对子项有边，子项对孙子有另一条边，并且父项对孙子也有边。我只是想删除孙子和父(根)之间的边缘，因为这会使我的图表复杂化。例如:我想从上图中删除 ('n', 'n131') 和 ('n', 'n221')。实现这一目标的最佳方法是什么。

Answer 1

看起来你想找到图 G 的最小生成树，你可以使用 Prim 或 Kruskal 的算法实现:这是一个来自 scipy 的:http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html