圖圖的表示法

圖圖的表示法第一頁，共二十六頁，2022年，8月28日圖的基本概念及基本術(shù)語圖的表示法圖的遍歷最小生成樹最短路徑拓?fù)渑判蛑饕獌?nèi)容第二頁，共二十六頁，2022年，8月28日27.2圖的存儲結(jié)構(gòu)鄰接矩陣表示法鄰接表表示法鄰接多重表十字鏈表第三頁，共二十六頁，2022年，8月28日3設(shè)圖A=(V,E)是一個有n個頂點(diǎn)的圖,圖的鄰接矩陣是一個二維數(shù)組A

[n][n]，定義：故，圖的鄰接矩陣表示法也稱為：數(shù)組表示法7.2.1鄰接矩陣(AdjacencyMatrix)第四頁，共二十六頁，2022年，8月28日4無向圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣可能是不對稱的。0123012第五頁，共二十六頁，2022年，8月28日5863129542031網(wǎng)的鄰接矩陣第六頁，共二十六頁，2022年，8月28日61.無向圖的鄰接矩陣是對稱矩陣，所以可采用壓縮存儲法（下三角），其存儲空間只需＿＿＿＿＿。2.有向圖的鄰接矩陣一定不是對稱矩陣，對嗎？3.有向圖的鄰接矩陣需要＿＿＿＿＿＿個存儲空間。練習(xí)n(n-1)/2n2不對！有可能是對稱矩陣第七頁，共二十六頁，2022年，8月28日7在有向圖中,統(tǒng)計第i

行1的個數(shù)可得頂點(diǎn)i的出度，統(tǒng)計第j列1的個數(shù)可得頂點(diǎn)j的入度。在無向圖中,統(tǒng)計第i

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

的度。第八頁，共二十六頁，2022年，8月28日8鄰接矩陣的C語言描述第九頁，共二十六頁，2022年，8月28日9第十頁，共二十六頁，2022年，8月28日10采用鄰接矩陣表示法創(chuàng)建有向網(wǎng)－P205見算法7.1思考：如何采用鄰接矩陣表示法創(chuàng)建有向網(wǎng)的其它操作？？？第十一頁，共二十六頁，2022年，8月28日11只須將實(shí)現(xiàn)有向網(wǎng)中邊的權(quán)值表示方式按如下修改即可每條邊的邊權(quán)規(guī)定為1，邊權(quán)為0時表示無邊用鄰接矩陣實(shí)現(xiàn)有向圖第十二頁，共二十六頁，2022年，8月28日12邊權(quán)規(guī)定為1，邊權(quán)為0時表示無邊一條邊可看作兩條相反方向的弧，如：-----插入一條邊(i,j)的操作：用鄰接矩陣實(shí)現(xiàn)無向圖G->arcs[i][j].adj=1;G->arcs[j][i].adj=1;第十三頁，共二十六頁，2022年，8月28日13優(yōu)點(diǎn)：易于操作缺點(diǎn)：對于稀疏圖來講，該方法極浪費(fèi)鄰接矩陣表示法解決方法：鄰接表表示法第十四頁，共二十六頁，2022年，8月28日14鄰接表表示法內(nèi)容結(jié)束之后回第十五頁，共二十六頁，2022年，8月28日15鄰接表(AdjacencyList)表示法ABCDvexdatafirstarcABCD0123adjvexnextarc130210無向圖的鄰接表表頭結(jié)點(diǎn)表邊表表頭結(jié)點(diǎn)表下標(biāo)可從1開始也可從0開始第十六頁，共二十六頁，2022年，8月28日16ABCABC012ABC012102011有向圖的鄰接表鄰接表(出邊表)逆鄰接表(入邊表)vexdatafirstarcadjvexnextarcvexdatafirstarcadjvexnextarc第十七頁，共二十六頁，2022年，8月28日17BACD69528ABCD01231

53

62

83

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

9vexdatafirstarcadjvexinfonextarc第十八頁，共二十六頁，2022年，8月28日18優(yōu)點(diǎn)：不必存儲不存在的邊（?。┤秉c(diǎn)：結(jié)構(gòu)較復(fù)雜如建立逆鄰接表，方便計算入度，但實(shí)際上，一條邊需分別在鄰接表與逆鄰接表中存儲鄰接表表示法解決方法：十字鏈表（優(yōu)點(diǎn)一條弧只被存放一次）第十九頁，共二十六頁，2022年，8月28日19

十字鏈表“結(jié)點(diǎn)結(jié)構(gòu)”之后回第二十頁，共二十六頁，2022年，8月28日20弧結(jié)點(diǎn)：0312info35189013tailvex=0headvex=1hlink=?。?,1＞地址21tlink=?。?,2＞地址02info存儲弧的相關(guān)信息：如權(quán)值3第二十一頁，共二十六頁，2022年，8月28日21頂點(diǎn)結(jié)點(diǎn)：031B35189A1DDA0231B123D1firstin=?。?,0＞地址firstout=?。?,2＞地址data存儲與頂點(diǎn)有關(guān)的信息,如：名字A第二十二頁，共二十六頁，2022年，8月28日22

十字鏈表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.連線第二十三頁，共二十六頁，2022年，8月28日23是有向圖的一種鏈?zhǔn)酱鎯Y(jié)點(diǎn)結(jié)構(gòu)優(yōu)點(diǎn)：計算出度、入度十分方便缺點(diǎn)：結(jié)構(gòu)較復(fù)雜十字鏈表表示法第二十四頁，共二十六頁，2022年，8月28日24

鄰接多重表內(nèi)容結(jié)束后回第二十五頁，共二十六頁，2022年，8月28日25是無向圖的一種存儲結(jié)構(gòu)優(yōu)點(diǎn)：提供更為方便的邊處理信息，如：

比較無向圖的鄰接