graph-algorithm

2熱

1答えて

グラフにはn個の頂点とm個のエッジがあります。グラフが接続を開始し、リストに表示されている順にエッジが削除されます。プロセスが終了すると、グラフは切断されます。したがって、削除する前にn/4個の頂点の床よりも1つ多い接続されたコンポーネントがあるように、エッジのリストに特定のエッジがあります。このエッジを除去した後、n/4個の頂点の床よりも大きいグラフには、連結成分はありません。どのように私は

5熱

1答えて

N個のレプリカを同期させるための再送回数を最小限に抑える方法は？

信頼できないマルチキャスト環境でメッセージ状態を同期させるために必要なメッセージ再送の回数を最小限に抑える、所定のサイズNのサブセットをどのように見つけるか（つまり、すべてのレプリカが他のすべてのレプリカのメッセージを確実に受信する）？レプリカのメッセージ状態は、それぞれが同じDソース（D> = M）のメッセージから成ります。各ソースについて、レプリカは、そのソースからいくつかの最高の序数までの

2熱

1答えて

コードチャレンジ - 時間

の限られた量の訪問の最大ノードこのサンプルタイミングマトリックス検討：（N×N個）を { {0, 2, 2, 2, -1}, {9, 0, 2, 2, -1}, {9, 3, 0, 2, -1}, {9, 3, 2, 0, -1}, {9, 3, 2, 2, 0} } 行0及びnは、それぞれ、開始位置と終了位置です。開始ノードと終了ノードは常にそれぞれで開始して終了する必要があ

0熱

1答えて

Dijkstraを変更して最大の色付きノードを持つパスを見つけよう

Dijkstraを修正して、K色のエッジを最大にして最短経路を得るという問題の解決策を見ただけです。エッジの代わりにカラーノードを使って最短経路を見つけたいのであれば、私たちはどのようにダイクストラを変えてこのトリックを行うのですか？私が思いつくのは、Dijkstraの上に、整数変数を追加してiと言うことです。次に、そこに到達するのに必要な着色ノードの数を記録する地図を作成し、色の薄いノードを通

-1熱

1答えて

グラフ：n個のエッジで最小ウェイトのパスを見つけるか？

無向グラフの場合、頂点Aから頂点Bまでのn個のエッジを持つパスの最小合計重みを求める必要があります。「ワイパーパスの問題」に関するWikipediaの記事が見つかりましたが、私の問題は同じように見えますが、そのアルゴリズムをいくつかのエッジでどのように拡張できますか？誰かが提案できるアルゴリズムはありますか？

0熱

4答えて

グラフを読むためにvector of vectorを使用するには？

#include <iostream> #include <vector> using namespace std; void addEdge(vector<vector<int> > adj, int, int); void print_graph(vector<vector<int> > adj); int main() { vector<vector<int> >

1熱

1答えて

2適合性が強く結びついたコンポーネントトポロジカルオーダー

私はSCCで2つの充足可能性の問題を解決しており、トポロジカルソートについて質問しています。私がこれをベースにしているアルゴリズムは、逆のトポロジカルな順序でSCCを処理することです。私のアルゴリズムは、このような場合に破壊されています。これは、このように見えるグラフを作る 3 3 -2 3 1 -2 -2 -1 ：あり二つのソースと、このグラフに2つのシンクがあり、そしてあなたがそこ

1熱

1答えて

与えられた数のノードとエッジを持つグラフを見つけるアルゴリズム

私はいくつかのノードを持ち、各ノードにはいくつかのエッジがあります。例：ノードAには3つのエッジがあり、Bには2があり、Cには2があり、Dには1があります。2つのノード間に複数のエッジを持たない無向グラフを見つけるアルゴリズムを探しています。この単純な例のために可能な解決策は、次のようになりますの A /|\ /| \ B--C D だからAは、それが3つの接続を持っているの

0熱

1答えて

動的プログラムを使用して最小限のエッジカバーを見つける効率的な方法

セルフループと平行エッジのない無向グラフを指定します。私の目的はminimum edge coverです。私はそれがbitmask DPを使用して効率的に行うことができることを知りました。私はたくさん試しましたが、state of DPの定義方法を理解することができません。 DPの状態を決定する際にお手伝いください。 dp[u][hashGuard] // curerntly in u node

3熱

1答えて

Dijkstraのアルゴリズムが各ラウンドでminを抽出することが必須であるのはなぜですか？

グラフがダイクストラのアルゴリズムを適用するのに有効である、すなわち負のエッジ重みがないと考えてください。 Dijkstraのアルゴリズムは、各ラウンドの最小距離ノードが抽出されるように選択されている場合にのみ機能します。最小距離ノード以外を抽出するとダイクストラのアルゴリズムが失敗するという証拠は何になるでしょうか？私は良い議論を探していますが、サポートの例は大歓迎です。