表示法
注意:
n個頂點e條邊的無向圖的鄰接表表示中有n個頂點表結點和2e個邊表結點。(換句話說，每條邊(i,j)在鄰接表 中出現兩次:一次在關於i的鄰接表中，另一次在關於j的鄰接表中)
有向圖
對於有向圖，vi的鄰接表中每個表結點都對應於以vi為始點射出的一條邊。因此，將有向圖的鄰接表稱為出邊表。
【例】有向圖G6如下圖所示，其中頂點v1的鄰接表上兩個表結點中的頂點序號分別為0和4，它們分別表示從v1射出的兩條邊(簡稱為v1的出邊):和。
注意:
n個頂點e條邊的有向圖，它的鄰接表表示中有n個頂點表結點和e個邊表結點。(因為有向圖是單向的)
逆鄰接表
在有向圖中，為圖中每個頂點vi建立一個入邊表的方法稱逆鄰接表表示法。
入邊表中的每個表結點均對應一條以vi為終點(即射入vi)的邊。
【例】G6的逆鄰表如上面(b)圖所示，其中v0的入邊表上兩個表結點1和3分別表示射人v0的兩條邊(簡稱為v0的入邊):和。
注意:
n個頂點e條邊的有向圖，它的逆鄰接表表示中有n個頂點表結點和e個邊表結點。
3.鄰接表的形式說明。
鄰接表是一個二維容器，第一維描述某個點，第二維描述這個點所對應的邊集們。
實現鄰接表的方法絕對有100種以上。即使是前向星這種東西也是鄰接表，因為它還是描述某個點和這個點所對應的邊集們.
我們說說常用的鄰接表存圖法(靜態的array就不說了.)必須有開O1以及以上編譯的條件，不然沒有測試的效率無任何意義。
第一維是描述點的。可以用vector,list,forward_list,deque,map,multimap,unordered_map,unordered_multimap等(一般不能用set,mutiset,unordered_set,unordered_multiset).
按照你的要求去選擇。一般來講存完圖以後不涉及點的加入與刪除優先使用vector.map,multimap,unordered_map,unordered_multimap.
第二維是描述這個點的邊集，可以用全部的容器。也是的一般來講存完圖以後,不涉及點的加入與刪除優先使用vector,空間充足可以考慮deque.涉及點的刪除用forward_list或者是list,map,multimap,unordered_map,unordered_multimap.
對於這個圖存儲的方法舉例(對於上面的圖):
第一種
對第一種方法有種最佳化就是對每個點所對應的邊的向量進行預估。例如有m條有向邊，n個點，那么每個向量需要reserve(6*(m/n)/5);一般這樣存儲效率會有顯著提高。
第二種(使用map,set)
方法太多，不再舉例了。
然而我們這樣存圖是不夠的，對於無向圖而言，可能存在一條邊需要知道自己的反向邊的位置。例如歐拉迴路，例如網路流都是需要的。
第二種方法由於std::map> graph;只是離散化後的鄰接矩陣。對於這種存圖方法，訪問反向邊則非常簡單，例如我訪問的是a->b這樣一條邊。那么只需要graph.count(a);就可以訪問其反向邊b->a。
然而對於第一種方法，我們沒有辦法解決反向邊的互相訪問題。
所以我們對於這種圖需要存圖修正。代碼如下:
對於list容器可以直接存疊代器的，但是存圖時也得考慮a是否等於b.forward_list存反向邊的圖就不好，因為用鍊表存圖就是需要存完圖後插入刪除，假定一個元素前面的元素被刪除了，那么根本無法訪問反向邊!!!!
感覺存圖沒問題了?NO!!!!還有一種圖更奇葩，那就是對於每個點中的邊得排序又得知道反向邊的那種圖。USACO上有個題目叫做騎馬修柵欄，那個題要求字典序輸出。數據量很小，以至於可以直接矩陣存圖，但是我們考慮如何數據量大，這種方法就不行了。如果用第二種方法(std::map>)存圖，絕對可可以，但是相對常數較大。如果我們考慮順序容器去存儲則比較快一些。
方法就是先用邊集表存圖，然後每條邊a,b得優先以std::min(a,b)為第一關鍵字再按std::max(a,b)為第二關鍵字排序，再按照修正後的存圖方法存圖即可。具體代碼見nocow上騎馬修柵欄那題lgeecn發的題解和代碼。
如果使用list存圖可以先存圖再用list.sort()函式進行排序，不過似乎效率會差一些,畢竟相對於vector,list常數太大了，達到6倍以上。
存圖真心不簡單，因為真正用的時候你可能會遇到各種問題，但是你可以加以思考，進行容器搭配使用，即可解決。
pascal程式
program ljb;
type
node=^link;
link=record
qu,g:longint;
next:node;
end;
var
nd:array[1..100000]of node;
n,m,i,u,v,w:longint;
procedure dfs(wei:longint);
var
p:node;
begin
writeln(wei);
p:=nd[wei];
while p<>nil do
begin
dfs(p^.g);
p:=p^.next;
end;
end;
procedure addd(u,v,w:longint); //建立鄰接表
var
p:node;
begin
new(p);
p^.g:=v;p^.next:=nd[u];p^.qu:=w;
nd[u]:=p;
end;
begin
readln(n,m); //n:結點數 m:邊數
for i:=1 to m do
begin
readln(u,v,w);
addd(u,v,w);
end;
dfs(1);//從1號節點開始dfs
end.
(應該沒有問題吧......)
(無向圖只要在addd過程中反過來再new一遍就可以了)
鄰接表