グラフの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. 特定のWHERE条件に基づいて特定のフィールドを選択する
- 6. パンダスの条件に基づいてNAを作成する
- 7. Matlab - 条件に基づいて特定の行を選択
- 8. 条件に基づいてPython辞書を作成する
- 9. 特定の条件に基づいてテーブルから特定の列をグレーアウト
- 10. PHP特定の条件に基づいて特定のテーブルに挿入
- 11. スクリプトは条件に基づいてリストを作成します
- 12. Ruby:配列を比較し、特定の条件に基づいて新しい配列を作成する
- 13. 特定の条件に基づいて新しい値を挿入する
- 14. Scalaの特定の条件に基づいて値を計算する方法
- 15. 特定の条件に基づいて異なる行を返すSQL
- 16. 特定の条件に基づいてArrayListからオブジェクトを削除する
- 17. 特定の条件に基づいて論理ベクトル要素を選択する
- 18. PHPの条件に基づいてXMLを生成する
- 19. 特定の条件に基づいてキーの数を調べるjavascript
- 20. 特定の条件に基づいてSSISの行を数える方法は?
- 21. リストから重複を削除するC#の条件に基づいての条件に基づいて
- 22. 特定の条件に基づいてManytoOneを取得します
- 23. R:特定の条件に基づいて行を選択します。
- 24. 列の条件に基づいて複数の範囲を作成する
- 25. 条件に基づいてPandas Dataframeを作成する方が良い
- 26. アプリケーションデザイン:条件に基づいて特定のユーザーに電子メールを送信
- 27. ランタイムコンテキストに基づいて検索条件を設定する
- 28. ページ・パラメータに基づいてRailsフォームの条件を作成する場合
- 29. 列内の条件に基づいてグループ/クラスを作成する
- 30. 条件に基づく特定の列の削除
後で最短パスアルゴリズムなどを実行するように頼んだら正確に教えてもらえますか?ただし、グラフの構造を変更することはできず、グラフがツリーであるかどうかに依存します。 –