圖的儲存 各種方式的優缺點

圖的儲存

***圖，通俗地說是由邊和點組成的，一條邊連接配接兩個點，邊會有權值（點也會有，直接用數組儲存即可，不做讨論）***。

設有 n n n個點， m m m條邊。

方式1.鄰接矩陣

設 f [ i ] [ j ] f[i][j] f[i][j]表示從 i i i到 j j j的邊的權值。

按題目要求，當 i i i到 j j j有多條邊時，選取貢獻最大的一條。

空間複雜度： O ( n 2 ) O(n^2) O(n2)。

優點：實作簡單，使用友善。

缺點：空間太大，一般的題目都存儲不下。

方式2.鄰接表

設 p [ i ] p[i] p[i]表示 i i i點的出度， g [ i ] [ j ] g[i][j] g[i][j]為從 i i i出發可到達的第 j j j個點， f [ i ] [ j ] f[i][j] f[i][j]表示 g [ i ] [ j ] g[i][j] g[i][j]對應的邊權。

空間複雜度：随機資料時一般小于 O ( n 2 ) O(n^2) O(n2)，當出現一個點與其餘的所有點相連時 O ( n ∗ m ) O(n*m) O(n∗m)。

優點：随機資料下空間較小。

缺點：極限資料浪費空間大。

方式3.邊集數組

設 f [ i ] . f r f[i].fr f[i].fr， f [ i ] . t o f[i].to f[i].to， f [ i ] . l e n f[i].len f[i].len分别表示第 i i i條邊的起點、終點和權值。

空間複雜度： O ( m ) O(m) O(m)

優點：節約空間。

缺點：搜尋時需要把所有的邊枚舉一遍，太浪費時間。

方式4.排序前向星

和上一點類似。

在邊集數組的基礎上按 f [ i ] . f r f[i].fr f[i].fr排序，然後設 h [ i ] h[i] h[i]表示以 i i i為起點的邊在 f f f數組中最早出現的位置，每次隻需從 f [ h [ x ] ] f[h[x]] f[h[x]]開始往下搜尋，直到目前的 f [ i ] ≠ x f[i]≠x f[i]̸​=x。

優點：節約空間。

缺點：排序時間大。

方式5.鍊式前向星

f f f數組同上。我們想辦法減去排序的時間。

設 l a s t [ i ] last[i] last[i]表示以 i i i為起點的邊在 f f f數組中最後一次出現的位置，設 n e x t [ i ] next[i] next[i]表示起點為 f [ i ] . f r f[i].fr f[i].fr的邊在第 i i i條邊之前上一次出現的位置。

從 i = l a s t [ x ] i=last[x] i=last[x]開始，每次 i = n e x t [ i ] i=next[i] i=next[i]，直到 i = 0 i=0 i=0，即可快速找出所有以 x x x為起點的邊。

void add(int x,int y,int l)
	{
		f[++num].fr=x,f[num].to=y,f[num].len=l;
		next[num]=last[x];
		last[x]=num;
	}
	void find(int x)
	{
		for(i=last[x];i;i=next[i]) search();
	}
           

優點：快速且節約空間。

缺點：暫無。

以上為圖的儲存各種方式，我們要按照需要選取最合适的方式。