在不知道邻接矩阵大小的情况下存储邻接矩阵的最有效方法是什么？
我需要在邻接矩阵上存储具有多个节点（大小未知......可能很大）的非有向图。 2D arrayList 是存储它的有效方法吗？如果没有，存储这些数据的更好方法是什么？任何评论表示赞赏。
I need to store a non directed graph with multiple nodes (unknown to the size.. can be vast) on an adjacency matrix. Would a 2D arrayList be an efficient way to store this? If not, what is a better way to store this data? Any comment is appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我肯定会选择 2d ArrayList。如果在末尾插入（这是有意义的），您可以在 O(n) 时间内添加行/列（n 是行数）。访问列表的时间复杂度为 O(1)，删除任意行的时间复杂度为 O(n2)。
另一种选择是使用双向链表。在这种情况下，插入到末尾将是 O(n) 时间，访问是 O(n)，删除行是 O(n2)。
所以看起来对于矩阵来说，ArrayList是最好的，但只是因为访问效率更高。
I would definitely go for a 2d ArrayList. You can add rows/columns in O(n) time (n is the number of rows), if inserting at the end (which make sense). Access to the list is O(1), and removing an arbitrary row will be O(n2).
The other option is to use a doubly linked list. In this case, insertion to the ends will be O(n) time, access is O(n), and removing a row is O(n2).
So it seems that for a matrix, the ArrayList is best, but only because of more efficient access.
您说邻接列表可能是“巨大的”。如果它也是稀疏的，那么使用某种稀疏矩阵表示可能会更好。由于显着减少了内存占用，它甚至可能优于 2d ArrayList。
You say that the adjacency list could be "vast." If it is also sparse, you may be better off with some sort of sparse matrix representation. It might even be that, because of a vastly reduced memory footprint, it outperforms a 2d ArrayList.
我认为如果您还将图形的大小存储在文件的第一行中会更容易。这样分配和整个过程就会更加高效，而不会在其他方面造成任何损失。
如果您需要在增加矩阵时进行分配，则应该从相关域的合理大小开始，然后以 2 的乘数增加它，以便随着时间的推移，分配量趋于稳定，并且您不必多次重新分配和重新复制内容。
希望有帮助！
I think it would be easier if you would also store the size of the graph in the first line of the file. That way the allocation and whole process would be much more efficient, without a bit loss in anything else.
In case you need to do allocations as you increase the matrix, you should start with a reasonable size for the domain in question, and thing increase it with a multiplier of 2, so that along the time, the ammount of allocations tends to stabilize and you do not have to reallocate and recopy the contents as many times.
Hopes that helps!