将邻接矩阵转换为距离或跳跃矩阵

Question

是否可以按照定义转换 1 和 0 的邻接矩阵 here进入定义的距离矩阵 here其中每个链接的单位长度为 1？

Answer 1

1 和 0 的邻接矩阵只是无向图的表示。要获取未加权图的任意两个顶点之间的距离，可以使用 breadth first search .

假设您有一个 n by n 矩阵:

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