data-structures - 这种类型的图表示矩阵叫什么？

Question

在几年前的算法课程中，我遇到了一个有趣的图形表示。它基本上是一个路径矩阵，但有额外的信息。每个单元格都包含（可能为空的）与您可以通过到达Aij的顶点相邻的列表。ij

例如，有向图非正式地表示为：

(Z → X) (Z → Y) (X → W) (Y → W)

得到以下矩阵：

当维护这样的矩阵时，您不仅可以知道是否存在从i到的路径j，还可以知道所有可能的路径是什么。

但我终其一生都无法在网络上找到对这种表示的任何参考。它叫什么？

Answer 1

我相信它被称为邻接列表矩阵。请参阅http://www.dmi.usherb.ca/~hlaoui/th.pdf或在 Google Scholar 中搜索

Answer 2

经过大量搜索和一位老老师的提示，我找到了维基百科文章中关于Floyd-Warshall 算法的路径重建部分。他们将“下一个节点”存储在他们所谓的单元格之间的最短路径中：ijAij

下一个矩阵

在一组似乎是我的同事的幻灯片中，它被称为：

距离下一个表

在相同的上下文中。当然，他们正在谈论仅存储最短路径的信息。当然，为此目的，每个单元只存储一个节点（-index）就足够了。这些来源都没有引用任何科学出版物。但是找了半天，我强烈觉得我原来的问题中的矩阵表示从来没有正式命名过。所以，我给你配音：

路径下一个矩阵

如果有人可以引用其他说法的科学出版物，我仍然很乐意接受他们的回答而不是我自己的回答。