【文章內容簡介】 coutvertex[v]。visited[v]=1。Q[++rear]=v。while(front!=rear){v=Q[++front]。for(j=0。jvertexNum。j++)if(arc[v][j]==1amp。amp。visited[j]==0){coutvertex[j]。visited[j]=1。Q[++rear]=j。}}}圖的存儲結構及實現數據結構（ C＋＋版）清華大學出版社鄰接表鄰接表存儲的基本思想：對于圖的每個頂點 vi， 將所有鄰接于 vi的頂點鏈成一個單鏈表，稱為頂點 vi的 邊表 （對于有向圖則稱為出邊表），所有邊表的頭指針和存儲頂點信息的一維 數組構成了 頂點表 。 圖的存儲結構及實現圖的鄰接矩陣存儲結構的空間復雜度？如果為稀疏圖則會出現什么現象？假設圖 G有 n個頂點 e條邊，則存儲該圖需要 O(n2)數據結構（ C＋＋版）清華大學出版社鄰接表有兩種結點結構：頂點表結點和邊表結點 。vertex firstedge adjvex next頂點表 邊 表 vertex： 數據域，存放頂點信息。 firstedge： 指針域，指向邊表中第一個結點。 adjvex： 鄰接點域，邊的終點在頂點表中的下標。next： 指針域，指向邊表中的下一個結點。 圖的存儲結構及實現數據結構（ C＋＋版）清華大學出版社structArcNode{intadjvex。ArcNode*next。}。templateclassTstructVertexNode{Tvertex。ArcNode*firstedge。}。定義鄰接表的結點 圖的存儲結構及實現vertex firstedgeadjvex next數據結構（ C＋＋版）清華大學出版社103 ∧2 3 ∧1 ∧0 1 ∧V1V2V3V40123vertexfirstedge圖的存儲結構及實現V1V3V4V2無向圖的鄰接表邊表中的結點表示什么？每個結點對應圖中的一條邊，鄰接表的空間復雜度為 O(n+e)。數據結構（ C＋＋版）清華大學出版社103 ∧2 3 ∧1 ∧0 1 ∧V1V2V3V40123vertexfirstedge圖的存儲結構及實現V1V3V4V2無向圖的鄰接表如何求頂點 i 的度？頂點 i的邊表中結點的個數。數據結構（ C＋＋版）清華大學出版社如何判斷頂點 i 和頂點 j之間是否存在邊 ?測試頂點 i 的邊表中是否存在終點為 j 的結點。圖的存儲結構及實現103 ∧2 3 ∧1 ∧0 1 ∧V1V2V3V40123vertexfirstedgeV1V3V4V2無向圖的鄰接表數據結構（ C＋＋版）清華大學出版社圖的存儲結構及實現有向圖的鄰接表V1 V2V3 V41 2 ∧2 ∧0 ∧V1V2V3V40123vertexfirstedge∧如何求頂點 i 的出度？頂點 i 的出邊表中結點的個數。數據結構（ C＋＋版）清華大學出版社圖的存儲結構及實現有向圖的鄰接表V1 V2V3 V41 2 ∧2 ∧0 ∧V1V2V3V40123vertexfirstedge∧如何求頂點 i 的入度？各頂點的出邊表中以頂點 i 為終點的結點個數。數據結構（ C＋＋版）清華大學出版社圖的存儲結構及實現有向圖的鄰接表V1 V2V3 V41 2 ∧3 ∧0 ∧V1V2V3V40123vertexfirstedge∧如何求頂點 i 的所有鄰接點？遍歷頂點 i 的邊表，該邊表中的所有終點都是頂點 i 的鄰接點。數據結構（ C＋＋版）清華大學出版社圖的存儲結構及實現網圖的鄰接表V1 V2V3 V4278521V1V2V3V40123vertexfirstedge∧52 ∧83 ∧70 ∧數據結構（ C＋＋版）清華大學出版社鄰接表存儲有向圖的類 constintMaxSize=10。//圖的最大頂點數templateclassTclassALGraph{public:ALGraph(Ta[],intn,inte)。~ALGraph。voidDFSTraverse(intv)。voidBFSTraverse(intv)。private:VertexNodeadjlist[MaxSize]。intvertexNum,arcNum。}。圖的存儲結構及實現數據結構（ C＋＋版）清華大學出版社鄰接表中圖的基本操作 —— 構造函數 1.確定圖的頂點個數和邊的個數；2.輸入頂點信息，初始化該頂點的邊表；3.依次輸入邊的信息并存儲在邊表中；輸入邊所依附的兩個頂點的序號 i和 j；生成鄰接點序號為 j的邊表結點 s； 將結點 s插入到第 i個邊表的頭部；圖的存儲結構及實現數據結構（ C＋＋版）清華大學出版社templateclassTALGraph::ALGraph(Ta[],intn,inte){vertexNum=n。arcNum=e。for(i=0。ivertexNum。i++)//輸入頂點信息，初始化邊表{adjlist[i].vertex=a[i]。adjlist[i].firstedge=NULL。}圖的存儲結構及實現鄰接表中圖的基本操作 —— 構造函數 數據結構（ C＋＋版）清華大學出版社sfor(k=0。karcNum。k++)//輸入邊的信息存儲在邊表中{cinij。s=newArcNode。sadjvex=j。 snext=adjlist[i].firstedge。adjlist[i].firstedge=s。}}圖的存儲結構及實現12V1V2V3V40123∧∧∧∧①②數據結構（ C＋＋版）清華大學出版社鄰接表中圖的基本操作 —— 深度優(yōu)先遍歷templateclassTvoidALGraph::DFSTraverse(intv){coutadjlist[v].vertex。visited[v]=1。p=adjlist[v].firstedge。while(p!=NULL){j=padjvex。if(visited[j]==0)DFSTraverse(j)。 p=pnext。}}圖的存儲結構及實現數據結構（ C＋＋版）清華大學出版社鄰接表中圖的基本操作 —— 廣度優(yōu)先遍歷templateclassTvoidALGraph::BFSTraverse(intv){front=rear=1。coutadjlist[v].vertex。visited[v]=1。Q[++rear]=v。while(front!=rear){v=Q[++front]。p=adjlist[v].firstedge。while(p!=NULL){j=padjvex。if(visited[j]==0){coutadjlist[j].vertex。visited[j]=1。Q[++rear]=j。}p=pnext。}}}圖的存儲結構及實現數據結構（ C＋＋版）清華大學出版社十字鏈表 鄰接表圖的存儲結構及實現逆鄰接表將鄰接表與逆鄰接表合二為一 ?為什么要合并？V1 V2V3 V41 2∧3∧0v1v2v3v4∧0123 1∧3∧0∧2∧v1v2v3v401230 3∧數據結構（ C＋＋版）清華大學出版社十字鏈表的結點結構vertex firstin firstout頂點表結點tailvex headvex headlink taillink邊表結點tailvex： 弧的起點在頂點表中的下標；headvex： 弧的終點在頂點表中的下標；headlink： 入邊表指針域；taillink： 出邊表指針域。圖的存儲結構及實現vertex： 數據域，存放頂點信息；firstin： 入邊表頭指針；firstout： 出邊表頭指針；數據結構（ C＋＋版）清華大學出版社30 31∧3210 V1V2V3V423∧01 02∧圖的存儲結構及實現十字鏈表存儲有向圖 ∧∧V1 V2V3 V4∧∧∧v3v4v4v1v1v2 v1v3v4v2數據結構（ C＋＋版）清華大學出版社圖的存儲結構的比較 —— 鄰接矩陣和鄰接表O（ n2）O（ n+e）O（ n2）O（ n+e）空間性能 時間性能 適用范圍 唯一性鄰接矩陣鄰接表稠密圖稀疏圖唯一不唯一圖的存儲結構及實現數據結構（ C＋＋版）清華大學出版社圖的連通性要想判定一個無向圖是否為連通圖，或有幾個連通分量，通過 對無向圖遍歷即可得到結果。216。非連通圖：需從多個頂點出發(fā)進行搜索，而每一次從一個新的起始點出發(fā)進行 搜索過程中得到的頂點訪問序列恰為其各個連通分量中的頂點集。 216。連通圖：僅需從圖中任一頂點出發(fā)，進 行深度優(yōu)先搜索（或廣度優(yōu)先搜索），便可訪問到圖中所有頂點。 無向圖的連通性數據結構（ C＋＋版）清華大學出版社1. count=0。2.for(圖中每個頂點 v)1. if(v尚未被訪問過 )2. count++。3. 從 v出發(fā)遍歷該圖；4. 3.if(count==1)cout圖是連通的 。elsecout圖中有 count個連通分量 。求無向圖的連通分量圖的連通性數據結構（ C＋＋版）清華大學出版社有向圖的連通性⑴ 從某頂點出發(fā)進行深度優(yōu)先遍歷，并按其所有鄰接點都訪問（即出棧）的順序將頂點排列起來。⑵ 從最后完成訪問的頂點出發(fā)，沿著以該頂點為頭的弧作逆向的深度優(yōu)先遍歷。若不能訪問到所有頂點，則從余下的頂點中最后訪問的那個頂點出發(fā)，繼續(xù)作逆向的深度優(yōu)先遍歷，直至有向圖中所有頂點都被訪問到為止。⑶ 每一次逆向深度優(yōu)先遍歷所訪問到的頂點集便是該有向圖的一個強連通分量的頂點集。圖的連通性數