如何从图中获取有向树？

Question

import networkx as nx
G = nx.Graph()
G.add_edge(1,2)
G.add_edge(2,3)
G.add_edge(3,5)
G.add_edge(4,6)
G.add_edge(1,6)
G.add_edge(2,6)
G.add_edge(7,8)
G.add_edge(9,8)
mst=nx.prim_mst(G)# a generator of MST edges

我有一棵树。如何获得以4为根的有向树？

- kalombo

Answer 1

要从节点4获取广度优先搜索的有向树：

tree = nx.bfs_tree(G, 4)

---

获取从节点4开始深度优先搜索的有向树：

tree = nx.dfs_tree(G, 4)

---

这些图表是按照以下方式生成的：

import matplotlib.pyplot as plt
import networkx as nx

G = nx.Graph()
G.add_edge(1,2)
G.add_edge(2,3)
G.add_edge(3,5)
G.add_edge(4,6)
G.add_edge(1,6)
G.add_edge(2,6)
G.add_edge(7,8)
G.add_edge(9,8)

tree = nx.bfs_tree(G, 4)
nx.draw(tree)
plt.savefig('/tmp/bfs_image.png')

- unutbu

Answer 2

也许@kalombo希望从以节点4为根的G的MST中得到一棵有方向的树。在这种情况下，您需要先构建MST的图形。例如：

T = nx.bfs_tree(nx.Graph(nx.prim_mst_edges(G)),4)

- Aric