0

假设我产生了以下邻接矩阵

     A B C D E F G H I    
   A 0 1 0 1 0 0 0 0 0
   B 1 0 0 0 0 0 0 0 0
   C 0 0 0 1 0 0 0 0 0
   D 1 0 1 0 0 0 1 0 0
   E 0 0 0 0 0 1 0 0 0
   F 0 0 0 0 1 0 0 0 0
   G 0 0 0 1 0 0 0 0 0
   H 0 0 0 0 0 0 0 0 1
   I 0 0 0 0 0 0 0 1 0

遍历以确认我可以从 G 到 B 的最佳方法是什么？自从

  [G][D] = true
  [A][D] = true
  [A][B] = true

G-->D-->A-->B

我知道 BFS/DFS，但对于我可以用这个矩阵做什么以便我可以为它实现 BFS/DFS 感到困惑。

感谢您提供任何帮助！

4

3 回答 3

2

如果您只需要查看是否可以到达某个节点，请使用BFS或DFS。

于 2011-02-15T11:38:32.877 回答
0

使用任何旧的图形搜索，例如：

于 2011-02-15T11:45:46.687 回答
0

如果将邻接矩阵自身相乘，您将得到一个包含所有长度为 2 的路径的矩阵，依此类推。

您的矩阵的 n 次方将显示所有节点之间长度为 n 的路径数。

当然，如果只需要两个节点之间的距离，则不必进行全矩阵乘法。

于 2011-02-15T11:54:31.263 回答