存儲樹和圖的數據？

在我試圖解決的大多數樹或圖問題中，輸入通常是整個樹或圖結構中的一個節點 - >葉節點或節點1 - >相鄰節點格式。存儲樹和圖的數據？

是否有常用結構的任意列表保存在存儲器中的數據，後來幫助於預期algorithm.For例如：

Say i have a list of graph nodes like: 

1 3 8 2 4.....# 1 is connected to 3 8 2 4...nodes 
2 5 1 3... # 2 is connected to 5 1 3...nodes 
3 1 2... #likewise 
. ... 
8 ......

所以如果我想使用隨機收縮算法（在我將不得不契約邊緣說我收縮1和8 ..我使用一個多鏈表的結構，其中鄰接列表上的每個節點指向其對應的行ie8在第一行指向第八節點

現在的問題，爲什麼我選擇這種結構來存儲數據？

合同是有效地做1〜8一個單一實體，

，所以我讀1的3起鄰接表和去三分之二鄰接表變化1至8和明年8的排使1至8現在去2的名單變化1到8 ....最後我追加1s列表到8並刪除重複..Yep，所以最後1從圖中刪除後收縮1和8

我想知道所有通常或很少使用的結構爲存儲樹和圖表，如果與algos algo名稱關聯？謝謝

來源

2014-10-20 sarat

存儲圖的一種常見方式是使用n-m atrix，其中n是圖中頂點的數量。如果你只是想存儲鄰接關係，如果X是矩陣，那麼X[i][j] = 1如果頂點j從頂點i和0可到達，否則。你也可以用這種方式存儲邊緣成本或邊緣能力。缺點當然是使用的內存量，O(n^2)而不是O(n+m)，其中m是邊的數量，但優點是對於每個可能的頂點對來說都是O(1)查找。

解決所有對最短路徑問題的弗洛伊德算法自然可以使用這樣的矩陣，以及更復雜的子立方算法來解決各種圖路徑問題，利用環上更快的矩陣乘法。

來源

2014-10-21 03:46:09 wookie919

你說如果我只是想存儲鄰接關係，還有更多嗎？ – sarat 2014-10-21 06:20:19

@sarat我以爲我已經給出了其他的例子，但對不起，如果我不清楚。 'X [i] [j] = c'可能意味着從'i'到'j'的邊緣成本是'c'，或者可能意味着從'i'到'j'的邊緣容量是'c' 。你可以存儲你喜歡的任何信息，真的。 – wookie919 2014-10-21 08:22:25

我明白你在說什麼，但是我所問的是結構性差異。你給我的是一個鄰接矩陣，其優點是用值表示邊權重，我在示例中提到的是一個多路鏈表，它有助於一個動態的刪除...我問有沒有更像這些？ – sarat 2014-10-21 09:28:29

存儲樹和圖的數據？

回答

相關問題