2

グラフのBFSツリーとDFSツリーが最小スパニングツリーではなく、隣接リストの順序は問題ではないことを私に尋ねる質問があります。 BFSのDFSとMSTのプロパティが、私は疑問に混乱しています。どのように問題に近づくべきですか? (ソリューションを探していない)特定の条件に基づいてグラフを作成する

+0

後で最短パスアルゴリズムなどを実行するように頼んだら正確に教えてもらえますか?ただし、グラフの構造を変更することはできず、グラフがツリーであるかどうかに依存します。 –

答えて

0

私の提案は、グラフからMSTを見つけるためのアルゴリズムを見て、それが単なるBFSまたはDFS検索ではない理由を考えることです。

どのアルゴリズムでも、トリッキーな部分を実際にテストするエッジケースを見つけることは実装の重要な部分です。あなたは簡単な例から始めて、簡単なBFS/DFS検索が失敗するような方法で新しいエッジを追加したり、入力を変更したりすることができます。

隣接関係リストの順序とは独立している必要があるという条件は、テストグラフが本当に難しい構造であることを保証することです。

1

k頂点の完全なグラフを想像してみてください。 k > 3の場合、DFSツリーは常にBFSツリーとは異なるように見えます。 k > 4の場合は、BFSDFSの両方のツリーと異なる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の縁部を有しています。

関連する問題