C中的圖實現

我想知道什麼是實現圖數據結構及其相關算法的最佳和最快的方法。C中的圖實現

但我不明白的大圖時，我想找到兩個頂點v1和v2

我將不得不通過數組這將是O(n)遍歷之間的邊緣。

我的理解是否正確，或者有更好的方法來完成這件事。

2011-03-30 Avinash

您確實必須遍歷列表，但這通常不是問題，因爲大多數圖算法都會查看給定頂點的所有邊，因此遍歷列表的開銷爲O（ 1）爲每個邊緣。雖然如果你需要檢查一個邊是否存在，比如（v1，v2），那麼可能是一個鄰接矩陣更適合你的情況 – davin 2011-03-30 20:08:36

這種情況對於巨大的圖有多好？ – Avinash 2011-03-30 20:10:00

這取決於你的情況，它的查找速度更快，但內存更多。你有內存/速度限制嗎？如果是這樣，什麼更重要，什麼更少？你是否有一套特定的算法，你會執行，如果是的話，然後定製你的數據結果來優化這些算法... – davin 2011-03-30 20:13:29

首先，它不是O（n）。保持列表排序，它將是O（logN）。鄰接列表不一定需要通過鏈表來實現。有一個數組更常見。

另一種非常受歡迎的方法是鄰接矩陣n x n其中如果i和j連接，則a [i] [j]爲1（或邊的權重），否則爲0。這種方法對於具有許多邊的密集圖是最佳的。對於稀疏圖，相鄰列表往往更好

2011-03-30 20:10:32

您可以使用鄰接矩陣而不是列表。它會讓你很快找到邊緣，但它會佔用大量內存來處理大圖。

2011-03-30 20:08:06 Dima

實現圖的方法很多。你應該選擇一個最適合你的算法。一些想法：

a）全局節點和邊界列表。

b）全局節點列表，每節點邊緣列表。

c）中鄰接矩陣（A [i] [j] = W（邊緣連接VI-VJ如果它存在），否則爲0）

d）邊緣矩陣（A [i] [j] =如果Ei連接節點Vj，則爲1）

2011-03-30 20:17:42 slezica

回答