java - 在 Java 中构建稀疏矩阵而不使用哈希表？

Question

在我的项目中，我试图为图构建一个邻接矩阵，出于空间和时间的考虑，我们应该使用稀疏矩阵，根据我的理解，使用 HashMap 最容易完成。不幸的是，我们还必须实现一个邻接列表，我用所述 HashMap 实现了它，并且由于我们的邻接矩阵在结构上必须不同，所以我不能对矩阵使用 HashMap 。还有其他实现方法吗？

Answer 1

对于 n 维矩阵，您可以使用二叉树的变体。当插入等时，您所做的就是循环遍历维度，直到找到叶子。

因此，对于一个简单的二维数据集，例如按顺序插入 (2, 5)、(10, 1)、(5, 6)、(3, 4)，您将得到

 (2, 5)
    \
   (10, 1)
       \
      (5, 6)
        /
    (3, 4)

(2, 5) 被插入到根目录。

(10, 1) 向右，因为 10 > 2。

(5, 6) 位于 (2, 5) 的右侧，因为 5 > 2。然后它位于 (10, 1) 的右侧，因为 6 > 1。

(3, 4) 向右移动 3 > 2。然后向右 4 > 1。然后向左 3 < 5。