註意:
n個頂點e條邊的無向圖的鄰接表表示中有n個頂點表結點和2e個邊表結點。(換句話說,每條邊(i,j)在鄰接表 中出現兩次:壹次在關於i的鄰接表中,另壹次在關於j的鄰接表中) 對於有向圖,vi的鄰接表中每個表結點都對應於以vi為始點射出的壹條邊。因此,將有向圖的鄰接表稱為出邊表。
例有向圖G6如下圖所示,其中頂點v1的鄰接表上兩個表結點中的頂點序號分別為0和4,它們分別表示從v1射出的兩條邊(簡稱為v1的出邊):<v1,v0>和<v1,v4>。
註意:
n個頂點e條邊的有向圖,它的鄰接表表示中有n個頂點表結點和e個邊表結點。(因為有向圖是單向的) 在有向圖中,為圖中每個頂點vi建立壹個入邊表的方法稱逆鄰接表表示法。
入邊表中的每個表結點均對應壹條以vi為終點(即射入vi)的邊。
例G6的逆鄰表如上面(b)圖所示,其中v0的入邊表上兩個表結點1和3分別表示射人v0的兩條邊(簡稱為v0的入邊):<v1,v0>和<v3,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.
對於這個圖存儲的方法舉例(對於上面的圖):
第壹種: #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<std::size_t,std::set<std::size_t>> graph;只是離散化後的鄰接矩陣。對於這種存圖方法,訪問反向邊則非常簡單,例如我訪問的是a->b這樣壹條邊。那麽只需要graph[b].count(a);就可以訪問其反向邊b->a。
然而對於第壹種方法,我們沒有辦法解決反向邊的互相訪問題。
所以我們對於這種圖需要存圖修正。代碼如下: #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])//訪問點agraph[ele.first][ele.second];//這就是邊ele的反向邊了return0;}對於list容器可以直接存叠代器的,但是存圖時也得考慮a是否等於b.forward_list存反向邊的圖就不好,因為用鏈表存圖就是需要存完圖後插入刪除,假定壹個元素前面的元素被刪除了,那麽根本無法訪問反向邊!!!!
感覺存圖沒問題了?NO!!!!還有壹種圖更奇葩,那就是對於每個點中的邊得排序又得知道反向邊的那種圖。USACO上有個題目叫做騎馬修柵欄,那個題要求字典序輸出。數據量很小,以至於可以直接矩陣存圖,但是我們考慮如何數據量大,這種方法就不行了。如果用第二種方法(std::map<std::size_t,std::set<std::size_t>>)存圖,絕對可可以,但是相對常數較大。如果我們考慮順序容器去存儲則比較快壹些。
方法就是先用邊集表存圖,然後每條邊a,b得優先以std::min(a,b)為第壹關鍵字再按std::max(a,b)為第二關鍵字排序,再按照修正後的存圖方法存圖即可。具體代碼見nocow上騎馬修柵欄那題lgeecn發的題解和代碼。
如果使用list存圖可以先存圖再用list.sort()函數進行排序,不過似乎效率會差壹些,畢竟相對於vector,list常數太大了,達到6倍以上。
存圖真心不簡單,因為真正用的時候妳可能會遇到各種問題,但是妳可以加以思考,進行容器搭配使用,即可解決。