0

Python で基本的なスパニング ツリーを実装する方法がわかりません。重み付けされていないスパニング ツリー。

隣接リストを実装する方法を学びました：

for edge in adj1:
    x, y = edge[int(0)], edge[int(1)]
    if x not in adj2: adj2[x] = set()
    if y not in adj2: adj2[y] = set()
    adj2[x].add(y)
    adj2[y].add(x)
print(adj2)

しかし、「最も近い接続されていない頂点を見つける」を実装する方法がわかりません。

4

1 に答える 1

1

どのスパニング ツリー アルゴリズムを使用する必要があるかはわかりません。DFS? BFS? プリムは一定の重みを持っていますか? クラスカルは一定の重みを持っていますか？また、グラフは重み付けされていないため、「最も近い」接続されていない頂点とはどういう意味ですか? 特定の頂点 v に隣接するすべての頂点は、v から同じ距離になります。最後に、任意の頂点から開始することになっていますか? 0で？ユーザー指定の頂点で？0 と仮定して、あなたを正しい方向に押し進めようとします。

別のエッジに沿ってツリーに再度追加しないように、どの頂点が既にスパニング ツリーにあるかを表す何らかの方法が必要です。それはツリーでは起こりえないサイクルを形成します。あなたが与えた [ [1], [0,2,3], [1], [1] ] の例のように、ツリーを表現する方法が絶対に必要なので、物事を始める1つの方法は[ []、 []、[]、[]]。

また、最終的にすべてを 1 つのツリーに接続するようにする必要があります。たとえば、2 つのツリーを合わせてすべての頂点をカバーするが、エッジを介して互いに接続されていない状態で終了するのではありません。これを行うには 2 つの方法があります。 (1) 単一の頂点から開始し、すべてのノードをカバーするまで段階的にツリーを成長させて、複数のツリーが存在しないようにします。(2) 他の方法でエッジを追加し、接続されたコンポーネントを追跡して、最終的にすべてのコンポーネントを確実に接続できるようにします。(2) が必要だとわかっていない限り、(1) に固執することをお勧めします。

特定の質問に取り掛かる：入力inputgraph = [[1,2]、[0,2,3]、[0,1]、[1]]があり、currtree = [ []で始まる場合、 []、[]、[] ]、頂点 0 から開始し、inputgraph[0] を見て、0 が 1 と 2 に隣接していることを発見し、(0,1) または (0,2) のいずれかを選択します。ツリーの端になります。使用しているアルゴリズムが (0,1) を選択するように指示しているとしましょう。次に、currtree を [ [1], [0], [], [] ] に更新します。次に、アルゴリズムは、0 で別のエッジを選択するように指示します。これは、この入力グラフでは (0,2) である必要があります。または、1 でエッジを選択するように指示します。これは、(1,2) または (1,3) の可能性があります。 ）。(0,1) は既にツリー内にあるため、アルゴリズムは (1,0) が 1 で受け入れられる選択肢ではないという事実を追跡する必要があることに注意してください。

上に挙げたアルゴリズムのいずれか、または他のスパニング ツリー アルゴリズムを使用して、次にどの頂点を調べ、次にどのエッジを選択するかを体系化する必要があります。

考慮しなければならない問題と、抽象的なアルゴリズムの記述を実行中のコードにどのようにマッピングするかについてのアイデアが得られたことを願っています。アルゴリズムの学習はあなたに任せます！

于 2016-09-10T21:41:58.233 に答える