在 Java 中将有向无环图表示为二维数组

Question

如果每行都包含特定节点的直接外邻，我如何将有向无环图表示为二维数组。例如，如果我有一个数组 int [] [] 边，边 [0] = {1,2,3} 意味着从节点 0 到节点 1、2 和 3 都有边。

Answer 1

如果你必须使用2D数组 - 考虑到至少在Java中2D数组不能是稀疏的 - 那么你需要分配一个NxN数组： boolean[][] edges = new boolean[n][n];

1. 您需要允许所有节点所在的退化情况在单个链中，因此您需要n-1行。
2. 您需要允许在任何节点上根植的星号，因此n-1列。
将
3. 地址存储在数组中要复杂得多 - 考虑到无论如何大小都必须如此之大 - 比简单地在第 j 行存储"yes"要复杂得多，将 k 定位为来自 j -> k 的边缘。 更新后者要快得多。

显然，

明智的方法是从源节点到目标节点的哈希集的哈希映射，但这显然不是您要找的。

Answer 2

int n;
List<Integer>[] adj;
AdjacencyLists(int n) {
    adj = (List<Integer>[])new List[n];
    for (int i = 0; i < n; i++) 
        adj[i] = new ArrayList<Integer>(Integer.class);
}
.....
adj[a].add(b); // a -> b edge