關於在c中實現圖的數據結構的想法

Question

我想用C實現圖。我很困惑應該如何存儲每個節點。我首先想到使用鏈表，但我怎樣才能存儲連接到一個節點的下一個節點。

任何想法應該使用什麼數據結構，我應該如何使用它？

Answer 1

有一些衆所周知的方式來做到這一點。

一個是使用大小爲[n] [n]的二維數組，其中n是節點數。然後，如果存在從a到b的鏈接，則設置圖[a] [b] = 1。這種方法通常很快，但使用了大量的內存，特別是如果沒有那麼多的鏈接和許多節點的話。

另一種方法是爲所有節點製作一個列表（或一個數組），並將其中的每個人的內容設置爲指向動態數組或其鏈接的節點列表。

Answer 2

在圖形稀疏的情況下有用的數據結構是adjacency list（鏈接列表的鏈表），這是當頂點之間的連接（邊）很少時。

如果你的圖是dense然後使用adjacency matrix（nxn）2維數組，這是你的頂點之間有很多邊緣的情況。