在不知道其大小的情況下，存儲鄰接矩陣的最有效方法是什麼？

Question

我需要在一個鄰接矩陣上存儲一個帶有多個節點（大小未知的可能很大）的非有向圖。二維數組列表是一種有效的方法來存儲這個？如果不是，那麼存儲這些數據的更好方法是什麼？任何意見表示感謝，謝謝！

Answer 1

我肯定會去一個2d的ArrayList。您可以在O（n）時間（n是行數）中添加行/列，如果在末尾插入（這是有意義的）。訪問列表是O（1），刪除任意行將是O（n^2）。

另一種選擇是使用雙向鏈表。在這種情況下，插入到末尾將是O（n）時間，訪問是O（n），並且刪除行是O（n^2）。

因此，對於矩陣來說，ArrayList是最好的，但僅僅是因爲訪問效率更高。

Answer 2

我認爲，如果您還將圖形的大小存儲在文件的第一行，會更容易。這樣，分配和整個過程會更有效率，而其他任何方面都不會有任何損失。

如果你需要做的撥款爲你增加矩陣，你應該有問題的域名一個合理的規模開始，東西爲2的倍數增加，所以沿着時間，分配的ammount的趨向於穩定，你不必重新分配和重複內容多次。

希望有幫助！

Answer 3

你說鄰接表可能是「巨大的」。如果它也是稀疏的，那麼用某種稀疏矩陣表示可能會更好。它甚至可能因爲內存佔用大大減少而優於2d ArrayList。