java - 以最小成本（时间和空间）的图形表示

Question

我必须在java中表示一个图，但既不是邻接列表也不是邻接矩阵..

基本思想是，如果

deg[i]

是顶点 i 的退出度，那么它的邻居可以存储在

edges[i][j]在哪里

i <= j <= deg[i]

, 但鉴于

edges[][]

必须用一些值初始化，我不知道如何使它与邻接矩阵不同..

有什么建议么？

Answer 1

据我所知，用一种语言表示图形只有两种方法。

• 要么使用邻接矩阵
• 或使用发生矩阵

您可以制作一个关联矩阵，例如

         E1 E2 E3 E4      
  V1 1 2 1 1        
  V2 2 1 2 1        
  V3 1 1 1 2        
  V4 1 1 2 1

Answer 2

您正在与这个问题的下限作斗争。该图的两个主要表示已经非常适合它们各自的使用。

• 邻接列表，最小化空间。您将很难使用比每个边缘 1 个指针更少的内存。空间：O(V*E)。搜索：O(V)
• 邻接矩阵，非常快，代价是 v^2 空间。空间：O(V^2)。搜索：O(1)

因此，要制作对空间和时间都更好的东西，您必须将两者的想法结合起来。也意识到只会有更好的实际性能，理论上你不会提高 O(1) 搜索或 O(V*E) 大小。

我的想法是将所有图形节点存储在一个数组中。然后对于每个节点都有一个表示为位向量的邻接列表。这本质上是一个类似矩阵的表示，但仅适用于图中存在的那些节点，为您提供比矩阵更小的尺寸。由于可以针对位向量测试查询节点，因此搜索将比邻接列表略有改进。

还要检查稀疏矩阵表示。