問題タブ [spanning-tree]

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

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

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

次のような単純な無向グリッド ネットワークがあるとします。

また、各エッジにはその長さに対応する重みがあるとします。

グリッド内のすべてのスパニング ツリーと、それらに関連する合計の重みを計算するにはどうすればよいでしょうか?

注意: これは、すべての重みが 1 の場合の些細なケースです。

STP BPDU は、プロトコル ID フィールドとバージョン ID で始まります。バージョンが STP のタイプであることは理解しています。0 は STP、
2 は RSTP
、3 は MSTP を表します。
では、protocol id フィールドは何のために必要なのでしょうか? 0にならないのはいつ？

その背後にあるロジックは知っていますが、それを適用してコードを出力 8 に仕上げる方法がわかりません。

8 を取得する方法は、グラフの各頂点への最短経路を合​​計することでした。最短パスは、頂点の数が最も少ないパスです。同点の場合は、パスの重みをタイ ブレーカーとして使用します。

以下に示すようにサンプル入力を入力した後、コードを出力 8 に仕上げるのを手伝ってもらえますか?

入力：

4 6

女性 保守派 ネオコン 退役軍人

トランプ女性 1

トランプ保守党 1

トランプ・ネオコンズ 5

女性ネオコン 1

ネオコンズ ベテラン 5

保守党の退役軍人 1

出力：

8

グラフについては、以下の画像を見つけて ください。これが私のコードです。

ここをクリック

すべてのエッジに個別の重みを持つ連結グラフが与えられた場合、すべてのスパニング ツリー (最小スパニング ツリーを除く) には、より小さな重みを持つ隣接するスパニング ツリーがあることを示す必要があります。w(T') < w (T)、ここで T' はスパニング ツリー T に隣接しています。

私は、MST に隣接するすべての単一の ST に隣接するスパニング ツリー (実際には MST) があることを証明することに行き詰まっています。非 MST 隣接スパニング ツリーでこれを表示するにはどうすればよいですか?

この問題を解決しようとしている問題があります: (グリッド グラフ) M 2,4 にはいくつの異なるスパニング ツリーがありますか?

誰かがこの番号を見つける方法を説明できますか?

(クラスでキルヒホッフの定理や行列木を見なかったので、使用すべきではありません)

ありがとう

指定されたエッジのリストからスパニング ツリー リストを出力する方法を見つけようとしています。たとえば、私が読んだ場合：

0 1

2 1

0 2

1 3

次のスパニング ツリー リストを出力したい:

[[1]、[0,2,3]、[1]、[1]]

次のコードを使用して隣接リストを作成する方法を知っています。

ただし、スパニング ツリーの作成は別の話です。スパニング ツリーが重み付けされていないことを考えると、ここでプリムのアルゴリズムのいくつかのバージョンを使用する必要があるかどうかわかりません。

どんな助けでも大歓迎です！