第七章圖的表示法

第七章圖圖的基本概念及術(shù)語圖的表示法圖的遍歷圖的應(yīng)用本章目標(biāo)7.2圖的存儲結(jié)構(gòu)鄰接矩陣表示法鄰接表表示法鄰接多重表十字鏈表設(shè)圖A=(V,E)是一個有n個頂點(diǎn)的圖,圖的鄰接矩陣是一個二維數(shù)組A

[n][n]，定義：故，圖的鄰接矩陣表示法也稱為：數(shù)組表示法7.2.1鄰接矩陣(AdjacencyMatrix)無向圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣可能是不對稱的。0123012863129542031網(wǎng)的鄰接矩陣1.無向圖的鄰接矩陣是對稱矩陣，所以可采用壓縮存儲法（下三角），其存儲空間只需＿＿＿＿＿。2.有向圖的鄰接矩陣一定不是對稱矩陣，對嗎？3.有向圖的鄰接矩陣需要＿＿＿＿＿＿個存儲空間。練習(xí)n(n-1)/2n2不對！有可能是對稱矩陣在有向圖中,統(tǒng)計(jì)第i

行

1的個數(shù)可得頂點(diǎn)

i

的出度，統(tǒng)計(jì)第j列

1的個數(shù)可得頂點(diǎn)j

的入度。在無向圖中,統(tǒng)計(jì)第i

行(列)1的個數(shù)可得頂點(diǎn)i

的度。鄰接矩陣的C語言描述采用鄰接矩陣表示法創(chuàng)建有向網(wǎng)－P205見算法7.1思考：如何采用鄰接矩陣表示法創(chuàng)建有向網(wǎng)的其它操作？？？只須將實(shí)現(xiàn)有向網(wǎng)中邊的權(quán)值表示方式按如下修改即可

每條邊的邊權(quán)規(guī)定為1，邊權(quán)為0時表示無邊用鄰接矩陣實(shí)現(xiàn)有向圖邊權(quán)規(guī)定為1，邊權(quán)為0時表示無邊一條邊可看作兩條相反方向的弧，如：-----插入一條邊(i,j)的操作：用鄰接矩陣實(shí)現(xiàn)無向圖G->arcs[i][j].adj=1;G->arcs[j][i].adj=1;優(yōu)點(diǎn)：易于操作缺點(diǎn)：對于稀疏圖來講，該方法極浪費(fèi)鄰接矩陣表示法解決方法：鄰接表表示法鄰接矩陣表示法內(nèi)容結(jié)束之后回鄰接表(AdjacencyList)表示法ABCDvexdata

firstarcABCD0123adjvex

nextarc

130210無向圖的鄰接表表頭結(jié)點(diǎn)表邊表表頭結(jié)點(diǎn)表下標(biāo)可從1開始也可從0開始ABCABC012

ABC012102

011有向圖的鄰接表鄰接表(出邊表)逆鄰接表(入邊表)vexdata

firstarcadjvex

nextarcvexdata

firstarcadjvex

nextarcBACD69528ABCD0123

1

53

62

83

2(出邊表)(頂點(diǎn)表)有向網(wǎng)(帶權(quán)圖)的鄰接表1

9vexdata

firstarcadjvexinfonextarc優(yōu)點(diǎn)：不必存儲不存在的邊（?。┤秉c(diǎn)：結(jié)構(gòu)較復(fù)雜如建立逆鄰接表，方便計(jì)算入度，但實(shí)際上，一條邊需分別在鄰接表與逆鄰接表中存儲鄰接表表示法解決方法：十字鏈表（優(yōu)點(diǎn)一條弧只被存放一次）

十字鏈表“結(jié)點(diǎn)結(jié)構(gòu)”之后回弧結(jié)點(diǎn)：0312info35189013tailvex=0headvex=1hlink=?。?,3＞地址31tlink=弧＜0,2＞地址02info存儲弧的相關(guān)信息：如權(quán)值3頂點(diǎn)結(jié)點(diǎn)：031B35189A1DDA0231B123D1firstin=?。?,0＞地址firstout=?。?,2＞地址data存儲與頂點(diǎn)有關(guān)的信息,如：名字A

十字鏈表1.“圖例”后回并練習(xí)2.形式化定義與算法作圖方法：1.先畫出頂點(diǎn)結(jié)點(diǎn)（數(shù)組形式）2.畫出所有弧結(jié)點(diǎn)（剛弧尾將各弧結(jié)點(diǎn)放置在對應(yīng)的頂點(diǎn)結(jié)點(diǎn)后面）3.連線是有向圖的一種鏈?zhǔn)酱鎯Y(jié)點(diǎn)結(jié)構(gòu)優(yōu)點(diǎn)：計(jì)算出度、入度十分方便缺點(diǎn)：結(jié)構(gòu)較復(fù)雜十字鏈表表示法

鄰接多重表內(nèi)容結(jié)束后回是無向圖的一種存儲結(jié)構(gòu)優(yōu)點(diǎn)：提供更為方便的邊處理信息，如：

比較無向圖的鄰接表表示法中，每一條邊在鄰