圖的鄰接表存儲-九游会j9娱乐平台

❶ 鄰接表存儲時，空間復雜度o( n e)，還是o(n)

o(n e)，取n次最小權，每次取完會進行n次更新。如果能達到o（n e），就不需要o(n)。

在有向圖中，描述每個點向別的節點連的邊（點a->點b這種情況）。在無向圖中，描述每個點所有的邊。與鄰接表相對應的存圖方式叫做邊集表，這種方法用一個容器存儲所有的邊。

對於有向圖，vi的鄰接表中每個表結點都對應於以vi為始點射出的一條邊。因此，將有向圖的鄰接表稱為出邊表。

(1)圖的鄰接表存儲擴展閱讀：

n個頂點e條邊的有向圖，它的鄰接表表示中有n個頂點表結點和e個邊表結點。（因為有向圖是單向的）

在有向圖中，為圖中每個頂點vi建立一個入邊表的方法稱逆鄰接表表示法。入邊表中的每個表結點均對應一條以vi為終點(即射入vi)的邊。

n個頂點e條邊的有向圖，它的逆鄰接表表示中有n個頂點表結點和e個邊表結點。

❷ 用鄰接表存儲圖所用的空間大小與什麼有關

用鄰接表存儲圖所用的空間大小與圖的頂點數和邊數有關。有一個圖有n個頂點和e條邊，則在對應的鄰接表中，表頭向量大小等於頂點數。此圖是無向圖，則每條邊在鄰接表中出現兩次，即需要2e個存儲單元。此圖是有向圖，則每條邊只在鄰接表中出現一次，即需要p個存儲單元。由此可知用鄰接表存儲圖所用的空間大小與圖的頂點數和邊數都有關系。

❸ 稀疏圖為什麼用鄰接表存儲而不用鄰接矩陣我知道是空間效率問題，怎麼個說啊謝謝大神！

既然是稀疏圖 那麼每個節點的鄰居節點數目肯定少咯 當然用鄰接表（n個節點，用n*m個位置，m為每個節點的平均鄰居數目）
要是用鄰接矩陣的話 每個節點都要給鄰居空n-1個位置（n個節點，需要n*n個位置）
當m遠小於n時（稀疏圖就符合這種情況），當然鄰接表省空間。