グラフのBFSツリーとDFSツリーが最小スパニングツリーではなく、隣接リストの順序は問題ではないことを私に尋ねる質問があります。 BFSのDFSとMSTのプロパティが、私は疑問に混乱しています。どのように問題に近づくべきですか? (ソリューションを探していない)特定の条件に基づいてグラフを作成する
2
A
答えて
0
私の提案は、グラフからMSTを見つけるためのアルゴリズムを見て、それが単なるBFSまたはDFS検索ではない理由を考えることです。
どのアルゴリズムでも、トリッキーな部分を実際にテストするエッジケースを見つけることは実装の重要な部分です。あなたは簡単な例から始めて、簡単なBFS/DFS検索が失敗するような方法で新しいエッジを追加したり、入力を変更したりすることができます。
隣接関係リストの順序とは独立している必要があるという条件は、テストグラフが本当に難しい構造であることを保証することです。
1
k
頂点の完全なグラフを想像してみてください。 k > 3
の場合、DFS
ツリーは常にBFS
ツリーとは異なるように見えます。 k > 4
の場合は、BFS
とDFS
の両方のツリーと異なるMST
を使用できます。 MST
の形状をDFS
ツリーと異なるように選択することができます。これは、1つの頂点に3つのエッジが出てくるようにすることです。 MST
の形状をBFS
ツリーと異なるように選択することができます。頂点に3つ以上のエッジが出てこないようにします。 MST
の一部には、選択したエッジを作成するためにウェイトを割り当て、そのエッジのみを割り当てることによって、MST
の形状を選択します。
DFS Tree
1-----2----3
|
|
4-----5
BFS Tree
1
____|____
//\ \
2 3 4 5
MST
2
|
1---3---5
|
4
5つの頂点に完全グラフは4つだけが、任意のツリーに必要とされる5×4/2 = 10の縁部を有しています。
関連する問題
- 1. 特定の条件に基づいて新しい変数を作成する
- 2. 特定の条件に基づいてデータフレームを作成する方法
- 3. 条件に基づいて特定のセルをロックする
- 4. r条件に基づいてグループを特定する
- 5. ブール値を数える特定の条件に基づいて
- 6. 特定のWHERE条件に基づいて特定のフィールドを選択する
- 7. 条件の値に基づいて列を作成するR
- 8. は、行の条件に基づいて、列を作成する
- 9. パンダスの条件に基づいてNAを作成する
- 10. Matlab - 条件に基づいて特定の行を選択
- 11. 条件に基づいてPython辞書を作成する
- 12. 条件に基づいて変数を作成する
- 13. 特定の条件に基づいてテーブルから特定の列をグレーアウト
- 14. PHP特定の条件に基づいて特定のテーブルに挿入
- 15. Pythonは条件に基づいてサブリストを作成します
- 16. スクリプトは条件に基づいてリストを作成します
- 17. フィルタ条件を作成:2つのテーブルに基づいて
- 18. Ruby:配列を比較し、特定の条件に基づいて新しい配列を作成する
- 19. 特定の条件に基づいて新しい値を挿入する
- 20. Scalaの特定の条件に基づいて値を計算する方法
- 21. 特定の条件に基づいて論理ベクトル要素を選択する
- 22. VBA Excel - 特定の条件に基づいて行をグループ化する
- 23. ハスケルで特定の条件に基づいてツリーをフィルタリングする方法は?
- 24. 特定の条件に基づいてArrayListからオブジェクトを削除する
- 25. 特定の条件に基づいて異なる行を返すSQL
- 26. PHPの条件に基づいてXMLを生成する
- 27. シリーズの条件に基づいて新しいパンダの列を作成する
- 28. 特定の条件に基づいてSSISの行を数える方法は?
- 29. 特定の条件に基づいてキーの数を調べるjavascript
- 30. 列の値に基づいて条件を決定する
後で最短パスアルゴリズムなどを実行するように頼んだら正確に教えてもらえますか?ただし、グラフの構造を変更することはできず、グラフがツリーであるかどうかに依存します。 –