什麼是最有效的方式來存儲一個非有向圖？

Question

正如標題所說......在java中存儲連通圖的最有效方法是什麼？

例如可以說我有互相連接的各種方式的多個位置，我必須通過圖形來遍歷，看看它的連接..任何幫助/意見將是有益的感謝！

Answer 1

一個常用的表示法是由圖中所有節點索引的矩陣（二維數組），其中M[i,j] == true是否存在從節點i到j的有向邊。主題的一個變體是存儲兩個節點之間邊緣的長度/權重（缺失邊緣可能由值-1表示）。

Answer 2

使用adjacency matrix無對稱性，從而表示方向，而不是簡單的相鄰關係。

Answer 3

對於查找效率 - 使用布爾矩陣（真，如果有連接的節點，假如果沒有電弧）。爲了內存效率，將其中一個對象屬性定義爲其指向的（動態）對象列表。注意後者只會幫助圖表中有很多節點。

Answer 4

使用的incidence或adjacency矩陣將這樣的伎倆。

如果您使用的鄰接矩陣，一個sparse matrix可能是有效地使用，如果你有很多節點。 Colt提供了一個稀疏矩陣實現。信息取自this SO post。

另外，我之前已經成功地使用了JUNG，因此您可能需要仔細研究一下它們是如何實現有向圖的。

Answer 5

我缺少的東西？數據已經是一個圖表，只是將其序列化。對於矩陣的書面討論這個問題是完全不成熟的。