algorithm - 加重無向 G の BFS

Question

加重無向グラフで BFS を実行しようとしています。BFSアルゴリズムの入力として使用できるように、重み付きグラフを重みなしに変換するアルゴリズムを誰か教えてください。ありがとう。

Answer 1

加重無向グラフの変換を 1 つの非加重 He アルゴリズムで実行するのは非常に簡単です。隣接行列の非ゼロ要素を true に、ゼロ要素を false に変更することに要約されます。ただし、BFS を加重無向グラフにも適用できます。