圖的鄰接表存儲的表示
❶ 鄰接表的簡介
圖的鄰接矩陣存儲方法跟樹的孩子鏈表示法相類似，是一種順序分配和鏈式分配相結合的存儲結構。如這個表頭結點所對應的頂點存在相鄰頂點，則把相鄰頂點依次存放於表頭結點所指向的單向鏈表中。如詞條概念圖所示，表結點存放的是鄰接頂點在數組中的索引。對於無向圖來說，使用鄰接表進行存儲也會出現數據冗餘，表頭結點A所指鏈表中存在一個指向C的表結點的同時，表頭結點C所指鏈表也會存在一個指向A的表結點。
鄰接表是圖的一種最主要存儲結構,用來描述圖上的每一個點。對圖的每個頂點建立一個容器（n個頂點建立n個容器），第i個容器中的結點包含頂點Vi的所有鄰接頂點。實際上我們常用的鄰接矩陣就是一種未離散化每個點的邊集的鄰接表。
在有向圖中，描述每個點向別的節點連的邊（點a->點b這種情況）。
在無向圖中，描述每個點所有的邊(點a-點b這種情況)
與鄰接表相對應的存圖方式叫做邊集表，這種方法用一個容器存儲所有的邊。
工業上有很多非常好的圖庫的實現,例如C++的boost graph庫.如果可以，盡量用這些庫，這樣可以大大提高你的效率。
❷ 如何用鄰接表存儲圖結構
我看不太懂這個程序，不過我有些過圖的鄰接表表示，看對你有沒有幫助吧。
#include <iostream>
#include <fstream>
#include <vector>
typedef int QElemTyep;
#include "queue.h"
using namespace std;
typedef int Status;
#define MAX_VERTEX_NUM 30 //圖的最大頂點數
enum BOOL {False,True};
BOOL visited[MAX_VERTEX_NUM]; //全局變數--訪問標志數組
typedef struct ArcNode{
//弧結點
int adjvex; //該弧所指向的頂點的位置
struct ArcNode *nextarc; //指向下一條弧的指針
InfoType *info; //保存邊的信息，可以簡單的改為 int w;
}ArcNode;
typedef struct VNode{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
class Graph{
public: AdjList vertices; //記錄頂點信息，指向第一條依附該頂點的弧的指針
int vexnum,arcnum; //圖的當前頂點和弧數
int GraphKind; //圖的種類，0---無向圖，1---有向圖
Graph(int vexnum,int arcnum,int kind)
{
this->vexnum=vexnum;
this->arcnum=arcnum;
this->GraphKind=kind;
}
};
void CreateGraph(Graph &G,VertexType *V,ArcType *VR){
//構造鄰接表結構的圖G
int i;
ArcNode *s;
for(i=1;i<=G.vexnum;i++) //初始化指針數組
{
G.vertices[i].data=V[i];
G.vertices[i].firstarc=NULL;
}
for(i=1;i<=G.arcnum;i++)
{
s=(ArcNode *)malloc(sizeof(ArcNode)); //生成一個弧結點
s->nextarc=G.vertices[VR[i].start].firstarc; //插入到鄰接表中
s->adjvex=VR[i].end;
G.vertices[VR[i].start].firstarc=s;
if(G.GraphKind==0) {
//若是無向圖，再插入到終點的弧鏈中
s=(ArcNode *)malloc(sizeof(ArcNode));
s->nextarc=G.vertices[VR[i].end].firstarc;
s->adjvex=VR[i].start;
G.vertices[VR[i].end].firstarc=s;
}
}
}
❸ 用鄰接表表示圖進行深度優先遍歷時，通常採用（）來實現演算法
使用棧來實現演算法。
用鄰接表表示圖進行深度優先遍歷時，通常採用棧來實現演算法，廣度遍歷使用隊列。
擴展材料：
深度優先遍歷：類似與樹的前序遍歷。從圖中的某個頂點v出發，訪問此頂點，然後從v的未被訪問到的鄰接點進行遍歷，直到圖中所有和v有路徑相通的頂點都被訪問到
註：優先訪問外層節點，訪問到無新頂點時，會進行回退，訪問未被訪問過的分支頂點。
廣度優先遍歷：類似於樹的層序遍歷。從圖中的某個頂點w出發，讓頂點w入隊，然後頂點w再出隊，並讓所有和頂點w相連的頂點入隊，然後再出隊一個頂點t，並讓所有和t相連但未被訪問過的頂點入隊……由此循環，指定圖中所有元素都出隊。
參考資料來源：
知網論文-數據結構中圖的遍歷演算法研究
❹ 在用鄰接表表示圖時,對圖進行深度優先搜索遍歷的演算法的時間復雜度為()
因為當相鄰矩陣的大部分被破壞時，矩陣中的所有元素都需要掃並追蹤到，且元素個數為n＾2，自然演算法為O（n＾2）。
所以鄰接表只存儲邊或弧，如果掃描鄰接表，當然會得到O（n＋e）其中n是頂點的數量，e的邊或弧的數量。
設有n個點，e條邊
鄰接矩陣：矩陣包含n＾2個元素，在演算法中共n個頂點，對每個頂點都要遍歷n次，所以時間復雜度為O（n＾2）。
鄰接表：包含n個頭結點和e個表結點，演算法中對所有結點都要遍歷一次，所以時間復雜度為O（n+e）順便，對於廣度優先演算法的時間復雜度，也是這樣。
(4)圖的鄰接表存儲的表示擴展閱讀：
鄰接表是圖的最重要的存儲結構之一，描述了圖上的每個點。創建一個容器對於每一個圖的頂點（n頂點n容器）和節點在第i個容器包含所有相鄰頂點的頂點Vi。事實上，我們經常使用的鄰接矩陣是一個鄰接表的邊集不離散化每一個點。
在有向圖中，描述每個點與另一個節點連接的邊(在a點->點B)。
在無向圖中，描述每個點上的所有邊（A點和B點的情況）
鄰接表對應的圖存儲方法稱為邊集表。此方法將所有邊存儲在容器中。
❺ 圖的存儲結構——所存儲的信息有哪些
一、鄰接矩陣存儲方法
鄰接矩陣是表示頂點之間相鄰關系的矩陣。
設G=(V，E)是具有n（n＞0）個頂點的圖，頂點的順序依次為0～n-1，則G的鄰接矩陣A是n階方陣，其定義如下：
（1）如果G是無向圖，則：
A[i][j]=1：若(i,j)∈E(G) 0:其他
（2）如果G是有向圖，則：
A[i][j]=1：若<i,j>∈E(G) 0:其他
（3）如果G是帶權無向圖，則：
A[i][j]= wij ：若i≠j且(i,j)∈E(G) 0：i=j ∞：其他
（4）如果G是帶權有向圖，則：
A[i][j]= wij ：若i≠j且<i,j>∈E(G) 0：i=j∞：其他
注意：帶權圖和不帶權圖表示的元素類型不同。
帶權圖（不論有向還是無向圖）A[i][j]用double表示，不帶權圖（不論有向還是無向圖）A[i][j]用int表示。
用一維數組G[ ]存儲有4個頂點的無向圖如：G[ ] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }
則頂點2和頂點0之間是有邊的。
如：
鄰接矩陣的特點如下：
（1）圖的鄰接矩陣表示是唯一的。
（2）無向圖的鄰接矩陣一定是一個對稱矩陣。因此，按照壓縮存儲的思想，在具體存放鄰接矩陣時只需存放上（或下）三角形陣的元素即可。
（3）不帶權的有向圖的鄰接矩陣一般來說是一個稀疏矩陣。因此，當圖的頂點較多時，可以採用三元組表的方法存儲鄰接矩陣。
（4）對於無向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個數正好是第i個頂點的度。
（5）對於有向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個數正好是第i個頂點的出度（或入度）。
（6）用鄰接矩陣方法存儲圖，很容易確定圖中任意兩個頂點之間是否有邊相連。但是，要確定圖中有多少條邊，則必須按行、按列對每個元素進行檢測，所花費的時間代價很大。這是用鄰接矩陣存儲圖的局限性。
鄰接矩陣的數據類型定義如下：
#define MAXV <最大頂點個數>
typedef struct
{ int no; //頂點編號
InfoType info; //頂點其他信息
} VertexType; //頂點類型
typedef struct //圖的定義
{ int edges[MAXV][MAXV]; //鄰接矩陣
int n，e; //頂點數，弧數
VertexType vexs[MAXV]; //存放頂點信息
} MGraph; //圖的鄰接矩陣表示類型
二、 鄰接表存儲方法
圖的鄰接表存儲方法是一種順序分配與鏈式分配相結合的存儲方法。
在鄰接表中，對圖中每個頂點建立一個單鏈表，第i個單鏈表中的節點表示依附於頂點i的邊（對有向圖是以頂點i為尾的邊）。每個單鏈表上附設一個表頭節點。
其中，表節點由三個域組成，adjvex指示與頂點i鄰接的點在圖中的位置，nextarc指示下一條邊或弧的節點，info存儲與邊或弧相關的信息，如權值等。
表頭節點由兩個域組成，data存儲頂點i的名稱或其他信息，firstarc指向鏈表中第一個節點。
typedef struct ANode
{ int adjvex; //該邊的終點編號
struct ANode *nextarc; //指向下一條邊的指針
InfoType info; //該邊的相關信息
} ArcNode; //邊表節點類型
typedef struct Vnode
{ Vertex data; //頂點信息
ArcNode *firstarc; //指向第一條邊
} VNode; //鄰接表頭節點類型
typedef VNode AdjList[MAXV]; //AdjList是鄰接表類型
typedef struct
{ AdjList adjlist; //鄰接表
int n,e; //圖中頂點數n和邊數e
} ALGraph; //完整的圖鄰接表類型
鄰接表的特點如下：
（1）鄰接表表示不唯一。這是因為在每個頂點對應的單鏈表中，各邊節點的鏈接次序可以是任意的，取決於建立鄰接表的演算法以及邊的輸入次序。
（2）對於有n個頂點和e條邊的無向圖，其鄰接表有n個頂點節點和2e個邊節點。顯然，在總的邊數小於n(n-1)/2的情況下，鄰接表比鄰接矩陣要節省空間。
（3）對於無向圖，鄰接表的頂點i對應的第i個鏈表的邊節點數目正好是頂點i的度。
（4）對於有向圖，鄰接表的頂點i對應的第i個鏈表的邊節點數目僅僅是頂點i的出度。其入度為鄰接表中所有adjvex域值為i的邊節點數目。
例， 給定一個具有n個節點的無向圖的鄰接矩陣和鄰接表。
（1）設計一個將鄰接矩陣轉換為鄰接表的演算法；
（2）設計一個將鄰接表轉換為鄰接矩陣的演算法；
（3）分析上述兩個演算法的時間復雜度。
解：
（1）在鄰接矩陣上查找值不為0的元素，找到這樣的元素後創建一個表節點並在鄰接表對應的單鏈表中採用前插法插入該節點。
void MatToList(MGraph g，ALGraph *&G)
//將鄰接矩陣g轉換成鄰接表G
{ int i，j，n=g.n; ArcNode *p; //n為頂點數
G=(ALGraph *)malloc(sizeof(ALGraph));
for (i=0;i<n;i++) //給所有頭節點的指針域置初值
G->adjlist[i].firstarc=NULL;
for (i=0;i<n;i++) //檢查鄰接矩陣中每個元素
for (j=n-1;j>=0;j--)
if (g.edges[i][j]!=0)
{ p=(ArcNode *)malloc(sizeof(ArcNode));
//創建節點*p
p->adjvex=j;
p->nextarc=G->adjlist[i].firstarc;
//將*p鏈到鏈表頭
G->adjlist[i].firstarc=p;
}
G->n=n;G->e=g.e;
}
（2）在鄰接表上查找相鄰節點，找到後修改相應鄰接矩陣元素的值。
void ListToMat(ALGraph *G，MGraph &g)
{ int i，j，n=G->n;ArcNode *p;
for (i=0;i<n;i++)
{ p=G->adjlist[i].firstarc;
while (p!=NULL)
{ g.edges[i][p->adjvex]=1;
p=p->nextarc;
}
}
g.n=n;g.e=G->e;
}
（3）演算法1的時間復雜度均為O(n2)。演算法2的時間復雜度為O(n+e)，其中e為圖的邊數。
❻ 有向圖的鄰接表存儲如圖所示，請畫出其鄰接矩陣存儲結構
有向圖的鄰接表存儲如圖所示，其鄰接矩陣存儲如圖：
❼ 鄰接表的表示法
注意：
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>usingnamespacestd;intmain(){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(constauto&ele:graph[1])//對於全部屬於graph[1]這個容器的元素std::cout<<ele<<'';std::cout<<std::endl;//程序運行後輸出40，表示點1連接了4點和0點。return0;}對第一種方法有種優化就是對每個點所對應的邊的向量進行預估。例如有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倍以上。
存圖真心不簡單，因為真正用的時候你可能會遇到各種問題，但是你可以加以思考，進行容器搭配使用，即可解決。