-
鄰接表
鎖定
- 中文名
- 鄰接表
- 外文名
- adjacency list
- 分 類
- 順序分配和鏈式分配
- 性 質
- 存儲結構
- 作 用
- 存儲圖
鄰接表簡介
圖的鄰接表存儲方法跟樹的孩子鏈表示法相類似，是一種順序分配和鏈式分配相結合的存儲結構。如這個表頭結點所對應的頂點存在相鄰頂點，則把相鄰頂點依次存放於表頭結點所指向的單向鏈表中。如詞條概念圖所示，表結點存放的是鄰接頂點在數組中的索引。對於無向圖來説，使用鄰接表進行存儲也會出現數據冗餘，表頭結點A所指鏈表中存在一個指向C的表結點的同時，表頭結點C所指鏈表也會存在一個指向A的表結點。
[1]
鄰接表是圖的一種最主要存儲結構,用來描述圖上的每一個點。對圖的每個頂點建立一個容器（n個頂點建立n個容器），第i個容器中的結點包含頂點Vi的所有鄰接頂點。實際上我們常用的鄰接矩陣就是一種未離散化每個點的邊集的鄰接表。
在有向圖中，描述每個點向別的節點連的邊（點a-＞點b這種情況）。
在無向圖中，描述每個點所有的邊(點a-點b這種情況)
與鄰接表相對應的存圖方式叫做邊集表，這種方法用一個容器存儲所有的邊。
工業上有很多非常好的圖庫的實現,例如C++的boost graph庫.如果可以，儘量用這些庫，這樣可以大大提高你的效率。
鄰接表表示法
注意：
鄰接表有向圖
對於有向圖，vi的鄰接表中每個表結點都對應於以vi為始點射出的一條邊。因此，將有向圖的鄰接表稱為出邊表。
【例】有向圖G6如下圖所示，其中頂點v1的鄰接表上兩個表結點中的頂點序號分別為0和4，它們分別表示從v1射出的兩條邊(簡稱為v1的出邊)：和。
注意：
n個頂點e條邊的有向圖，它的鄰接表表示中有n個頂點表結點和e個邊表結點。（因為有向圖是單向的）
鄰接表逆鄰接表
入邊表中的每個表結點均對應一條以vi為終點(即射入vi)的邊。
注意：
n個頂點e條邊的有向圖，它的逆鄰接表表示中有n個頂點表結點和e個邊表結點。
鄰接表鄰接表的形式説明
鄰接表是一個二維容器，第一維描述某個點，第二維描述這個點所對應的邊集們。
實現鄰接表的方法絕對有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.
對於這個圖存儲的方法舉例(對於上面的圖):
第一種:
#include <vector>
#include <iostream>
using namespace std;
int main()
{
vector<vector<size_t>> graph(5);
graph[0].push_back(1);//V0->V1.
graph[1].push_back(4);//V1->V4.
graph[1].push_back(0);//V1->V0.
graph[2].push_back(1);//V2->V1.
graph[2].push_back(3);//V2->V3.
graph[3].push_back(0);//V3->V0.
graph[4].push_back(3);//V4->V3.
//假定要訪問點1.
for(const auto &ele:graph[1])//對於全部屬於graph[1]這個容器的元素
std::cout<<ele<<'';
std::cout<<std::endl;
//程序運行後輸出40，表示點1連接了4點和0點。
return 0;
}
對第一種方法有種優化就是對每個點所對應的邊的向量進行預估。例如有m條有向邊，n個點，那麼每個向量需要reserve(6*(m/n)/5);一般這樣存儲效率會有顯著提高。
第二種(使用map,set):
#include<map>
#include<set>
#include<iostream>
#include<cstddef>
#include<map>
#include<set>
intmain()
{
std::map<std::size_t,std::set<std::size_t>>graph;
graph[0].insert(1);//V0->V1.
graph[1].insert(4);//V1->V4.
graph[1].insert(0);//V1->V0.
graph[2].insert(1);//V2->V1.
graph[2].insert(3);//V2->V3.
graph[3].insert(0);//V3->V0.
graph[4].insert(3);//V4->V3.
//假定要訪問點1.
for(constauto&ele:graph[1])//對於全部屬於graph[1]這個容器的元素
std::cout<<ele<<'';
std::cout<<std::endl;
//程序運行後輸出04，表示點1連接了0點和4點。對map,set裏的元素進行遍歷是有序的
return0;
}方法太多，不再舉例了。
第二種方法由於std::map
然而對於第一種方法，我們沒有辦法解決反向邊的互相訪問題。
所以我們對於這種圖需要存圖修正。代碼如下:
#include<vector>
#include<iostream>
#include<utility>
#include<cstddef>
intmain()
{
std::vector<std::vector<std::pair<std::size_t,std::size_t>>>graph(5);//每條邊的第二個元素不能是迭代器！！會失效！！！！必須是下標!!!
//比如有一條a-b的邊，我們得讓它實現互訪。我們這裏假定a=2,b=4;
std::size_ta(2),b(4);
graph[a].push_back(std::make_pair(b,graph[b].size()+(a==b)));//Va->Vb.需要判定a是否等於b.
graph[b].push_back(std::make_pair(a,graph[a].size()-1));//Vb->Va,這個不需要判定a是否等於b.
//訪問反向邊的方法.
for(constauto&ele:graph[a])//訪問點a
graph[ele.first][ele.second];//這就是邊ele的反向邊了
return0;
}
對於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一遍就可以了
- 參考資料
-
- 1. C#與數據結構--圖的遍歷 ．abatei-cnblog．2008-06-06[引用日期2014-12-20]
