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