使用網絡從圖表中刪除邊緣

Question

我試圖將DiGraph轉換爲n-ary樹並按級別順序或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的最小生成樹，您可以使用普里姆的或Kruskal算法的實現：這裏是一個從SciPy的：http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html