最近、C++ でグラフ エッジからツリーを生成しようとしましたが、if 条件または for ループが多すぎます。私はPythonに注意を向けましたが、最小限の複雑なコードでツリーを生成しているようです。私はPythonが初めてなので、助けを求めています。同様の質問がフォーラムに投稿されていますが、解決しようとしている同じ問題を扱っていません。問題は、コストが 10 の 1---->2 のようなグラフ エッジがいくつかあることです。1--->3 コスト 20 など。ここで、「1」がルート ノードの場合、複数の可能なツリーをそのコストとともに生成したいと考えています。私のコードは次のようになると思います。
class Edge:
def __init__(v1, v2, v3):
self.v1 = v1
self.v2 = v2
self.v3 = v3
graph = [Edge(1, 2, 10), Edge(2, 4, 20)]
これは私が返すべきものです。
map = {}
map[1] = [Edge(1, 2)] Cost: 10
map[2] = [Edge(1, 2), Edge(2, 4)] Cost: 30
2 がルート ノードの場合。
map = {}
map[1] = [Edge(2, 4)] Cost: 20
過去5日間この問題に悩まされていて、解決に至らないようです。ただし、networkx モジュールを見ましたが、それらの API の使用方法がわかりません。:(
編集:要約すると、フォレストが与えられた場合、複数の一意の「ツリー」を生成するにはどうすればよいですか?