将邻接矩阵转换为距离或跳矩阵 [英] Convert adjacency matrix to a distance or hop matrix

问题描述

是否可以按照定义的距离矩阵 /Distance_matrix#Examples_and_uses"rel =" nofollow noreferrer>此处其中每个链接的单位长度为1?

Is it possible to convert an adjacency matrix of ones and zeros as defined here into a distance matrix as defined here where each link would be of unit length 1?

推荐答案

一和零的邻接矩阵只是无向图的表示.要获取未加权图的任意两个顶点之间的距离，可以使用宽度优先搜索

An adjacency matrix of ones and zeros is simply a representation of an undirected graph. To get the distances between any two vertices of an unweighted graph, you can use breadth first search.

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

Assuming you have an n by n matrix:

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

这篇关于将邻接矩阵转换为距离或跳矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！