關聯矩陣而不是鄰接矩陣

使用關聯矩陣數據結構而不是更廣泛的鄰接矩陣解決圖表上哪類問題的速度更快（用big-O表示）？關聯矩陣而不是鄰接矩陣

2010-09-08 psihodelia

我不確定很容易找到基於底層表示的計算上限。大部分算法的複雜性將取決於邊數或頂點的數量，而不是底層表示。無論是在鉛筆和紙張還是電腦上實施，任何複雜性的下限都將適用。是否認爲如果你有特定類別的問題，那麼可能會提及這些問題，我們可以嘗試找出答案。 – Gian 2010-09-08 12:44:54

如果N非常大，且圖形非常稀疏，則關聯矩陣爲MxN且鄰接矩陣爲NxN，則您將具有MxN 2010-09-08 15:13:06

結構的空間複雜性是：

鄰接：o（V^2）發病率：O（VE）

隨着該入射結構可以節省空間，如果有更多的頂點的後果比邊緣。

你可以看一些典型的圖操作的時間複雜度：

查找靠近頂點的所有頂點：調：O（V）公司：O（VE）

檢查兩個頂點是相鄰的：調：O（1）公司：O（E）

計數一個頂點的化合價：調：O（V）公司：O（E）

等。對於任何給定的算法，您可以使用如上所述的構建塊來計算哪種表示可以爲您提供更好的總體時間複雜度。

作爲最後一點，使用任何類型的矩陣對除了最密集的圖以外的所有圖形都是非常空間低效的，並且我建議不要使用任何類型的矩陣，除非有意識地排除了鄰接列表等替代方法。

2010-09-08 19:05:17 user168715

我有非常密集的圖形，幾乎每一個連接。 – psihodelia 2010-09-09 09:36:16

沒有辦法有效存儲稀疏矩陣嗎？ – CMCDragonkai 2014-10-06 01:16:42

我個人從來沒有在編程競賽或研究問題中找到關鍵矩陣表示的實際應用。我認爲這對證明某些定理或某些非常特殊的問題可能有用。一本書給出了一個「計算生成樹的數量」的例子，作爲這種表示有用的問題。

這種表示的另一個問題是，它存儲它是沒有意義的，因爲從邊界列表中動態計算它（從而回答給定單元格包含的內容）非常簡單。

但是，它看起來在超圖中更有用，但只有在密集的情況下。

所以我的意見是 - 它只適用於理論工作。

2010-09-08 19:06:15 Milo

回答