重み付きグラフがあるとします。ランダムノードから始めて、深さ優先探索（明示的なスタックを使用する反復アルゴリズムを変更）を使用して、特定の重み半径内に存在するノードを確認するにはどうすればよいですか？（このノードから特定の重みで到達可能です。）
質問する
178 次
1 に答える
3
Nodeグラフ内のノードを示すためにタイプを使用するとします。最も単純なケースでは、Nodeは単なる整数（int）である可能性があります。
通常、タイプの明示的なスタックを使用しますNode。あなたの場合、ペアのタイプであるpair<Node,int>タイプのスタックを使用できます。これは、開始点からこれまでの距離を表します。pair<A,B>intNode
Node u今、距離が離れていると仮定しますd。隣接する場合は、エッジの重みとしNode vます。次に、スタックにプッシュします。最初に、深さ優先探索の開始点であるwhereをプッシュします。wuvpair(v, d+w)pair(v0, 0)v0
于 2012-12-26T11:09:36.967 に答える