假设我有边缘
A -> C
A -> D
A -> E
B -> D
B -> E
为了最大化数据局部性，我会安排将 DAG 按此顺序存储在内存中（作为数组），以最小化节点与其依赖项之间的距离。
C, A, D, E, B
因此 A 与 C 的距离为 1、1 与 D、2 至 E 的距离。
并且 B 的距离为 1 到 E，2 到 D。
有没有这样做的算法的名称？如果没有，将如何实现这一点？
看起来你想要线性化 DAG。我不知道您是否将其用于依赖项解析。 Topological_sorting看起来很熟悉你的问题。此外，该程序tsort做了非常相似的事情。
但是，它是依赖线性化。
neel@gentoo:~$ tsort
C A
D A
E A
D B
E B
C
D
E
B
A
打印必须执行该任务的顺序。 如果有循环，它可能不起作用。 正如您提到的非循环，它是相关的。
我不知道是否有任何这样的算法用于data locality ordering string或类似的东西，但是看起来您的数据局部性字符串有一些问题。
如果C接近（1）到A并且也接近（1）到B并且B离A太远（4）怎么办，您将如何使用数据局部性字符串表示它？
我现在不知道你到底想做什么。如果要将依赖项简化以按正确的顺序执行任务，请执行拓扑排序。
以下是改善局部性的方法略有不同：
http://ceur-ws.org/Vol-733/paper_pacher.pdf
所描述的算法似乎更接近力导向图绘制算法，而不是拓扑排序。
您还应该阅读有关内存图形数据库（如imGraph）的论文