具有最小成本（时间和空间）的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）大小

我的想法是将所有图形节点存储在一个数组中。然后，每个节点都有一个表示为位向量的邻接列表。这本质上是一种类似于矩阵的表示法，但仅适用于图中存在的节点，使其比矩阵小。与邻接列表相比，搜索会稍微有所改进，因为可以根据位向量测试查询节点

也请查看sparse matrix representations