c - 隣接行列を距離またはホップ行列に変換します

Question

ここで定義されている1と0 の隣接行列を、ここで定義されている距離行列に変換することは可能ですか？ここ で、各リンクは単位長1になりますか？

Answer 1

1と0の隣接行列は、無向グラフの単なる表現です。重み付けされていないグラフの任意の2つの頂点間の距離を取得するには、幅優先探索を使用できます。

nbyn行列があると仮定します。

for each vertex i:
    initialize an nxn matrix M
    run breadth-first search starting at i
    copy distances into row i of M
    return M