python - グラフから有向木を取得するにはどうすればよいですか?

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 の有向ツリーを取得するにはどうすればよいですか?

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')

Answer 2

@kalombo は、ノード 4 をルートとする G の MST から有向ツリーを必要としている可能性があります。その場合、最初に MST のグラフを作成する必要があります。例えば

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