0
MSTと有向グラフに関する質問があります。 重み関数w:E→Rを持つグラフGがあり、Eグループ(u、v)からエッジeがあるとします。 eがMSTに含まれていないかどうかをチェックするo(E + V)のアルゴリズムを見つける必要があります。MSTに特定のエッジが含まれていないかを確認
MSTと有向グラフに関する質問があります。 重み関数w:E→Rを持つグラフGがあり、Eグループ(u、v)からエッジeがあるとします。 eがMSTに含まれていないかどうかをチェックするo(E + V)のアルゴリズムを見つける必要があります。MSTに特定のエッジが含まれていないかを確認
数値を重みとして使用する代わりに、数値のペアのベクトルを重みとして使用します。加算はコンポーネントごとに行われます。比較は第1の数字にあり、第2の数字との結びつきが分かれている。 (非常に便利なのは、Pythonがどのように不等式のためにタプルを比較するのかのデフォルトルールです)。
各エッジに割り当てられます。重みは(w(x), 0)
です。しかし、あなたの特別な要素e
の重量を(w(e), -1)
に割り当ててください。
MSTを検索します。元のグラフにe
を含むMSTがある場合に限り、MSTにはe
が含まれます。