2017-12-19 4 views
0

MSTと有向グラフに関する質問があります。 重み関数w:E→Rを持つグラフGがあり、Eグループ(u、v)からエッジeがあるとします。 eがMSTに含まれていないかどうかをチェックするo(E + V)のアルゴリズムを見つける必要があります。MSTに特定のエッジが含まれていないかを確認

答えて

1

数値を重みとして使用する代わりに、数値のペアのベクトルを重みとして使用します。加算はコンポーネントごとに行われます。比較は第1の数字にあり、第2の数字との結びつきが分かれている。 (非常に便利なのは、Pythonがどのように不等式のためにタプルを比較するのかのデフォルトルールです)。

各エッジに割り当てられます。重みは(w(x), 0)です。しかし、あなたの特別な要素eの重量を(w(e), -1)に割り当ててください。

MSTを検索します。元のグラフにeを含むMSTがある場合に限り、MSTにはeが含まれます。

関連する問題