我需要在邻接矩阵上存储具有多个节点（大小未知..可能很大）的无向图。2D arrayList 会是存储它的有效方法吗？如果不是，那么存储这些数据的更好方法是什么？任何评论表示赞赏。
问问题
1537 次
3 回答
4
我肯定会选择 2d ArrayList。如果在末尾插入（这很有意义），您可以在 O(n) 时间内添加行/列（n 是行数）。访问列表是 O(1)，删除任意行是 O(n 2 )。
另一种选择是使用双向链表。在这种情况下，插入到末尾将是 O(n) 时间，访问是 O(n)，删除一行是 O(n 2 )。
因此，对于矩阵来说，ArrayList 似乎是最好的，但这只是因为访问效率更高。
于 2011-02-16T21:18:30.677 回答
1
你说邻接列表可能是“巨大的”。如果它也是稀疏的，那么使用某种稀疏矩阵表示可能会更好。甚至可能由于内存占用大大减少，它的性能优于 2d ArrayList。
于 2011-02-16T22:13:17.903 回答
0
我认为如果您还将图形的大小存储在文件的第一行中会更容易。这样分配和整个过程就会更有效率，而不会在其他任何事情上造成一点损失。
如果您需要在增加矩阵时进行分配，您应该从相关域的合理大小开始，然后以 2 的倍数增加它，这样随着时间的推移，分配量趋于稳定并且您不必多次重新分配和复制内容。
希望有帮助！
于 2011-02-16T21:18:29.020 回答