問題タブ [strongly-connected-graph]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
46 問題
0
投票する
1
に答える
67
参照
algorithm - 最大エッジと最小エッジの差が最小になる強連結グラフを見つける
Strongly Connectedである有向加重グラフが与えられた場合。最大重みエッジと最小重みエッジの差が最小になるように、このグラフから強く接続されたサブグラフを見つける必要があります。
より明確にするために、エッジを削除した後もグラフが強く接続され、最大重みエッジと最小重みエッジの差が最小になるように、エッジを削除する必要があります。
次に例を示します。
最初の行は、このグラフの N ノードと M エッジの数です。次の M 行は、このグラフのエッジを表します。
選択された N ノード サブグラフにはエッジが含まれます。
最大重みエッジと最小重みエッジの差は、32 - 8 = 24 です。これは、すべての選択肢の中で最小です。
最適なソリューションを探しています。最大で3000 のノードと5000 のエッジがあります。