圖圖的表示法

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

[n][n]，定義：故，圖的鄰接矩陣表示法也稱為：數(shù)組表示法7.2.1鄰接矩陣(AdjacencyMatrix)4第四頁(yè)，共二十六頁(yè)，編輯于2023年，星期二無(wú)向圖的鄰接矩陣是對(duì)稱的;有向圖的鄰接矩陣可能是不對(duì)稱的。01230125第五頁(yè)，共二十六頁(yè)，編輯于2023年，星期二863129542031網(wǎng)的鄰接矩陣6第六頁(yè)，共二十六頁(yè)，編輯于2023年，星期二1.無(wú)向圖的鄰接矩陣是對(duì)稱矩陣，所以可采用壓縮存儲(chǔ)法（下三角），其存儲(chǔ)空間只需＿＿＿＿＿。2.有向圖的鄰接矩陣一定不是對(duì)稱矩陣，對(duì)嗎？3.有向圖的鄰接矩陣需要＿＿＿＿＿＿個(gè)存儲(chǔ)空間。練習(xí)n(n-1)/2n2不對(duì)！有可能是對(duì)稱矩陣7第七頁(yè)，共二十六頁(yè)，編輯于2023年，星期二在有向圖中,統(tǒng)計(jì)第i

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

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

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

53

62

83

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

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

十字鏈表“結(jié)點(diǎn)結(jié)構(gòu)”之后回20第二十頁(yè)，共二十六頁(yè)，編輯于2023年，星期二弧結(jié)點(diǎn)：0312info35189013tailvex=0headvex=1hlink=?。?,1＞地址21tlink=?。?,2＞地址02info存儲(chǔ)弧的相關(guān)信息：如權(quán)值321第二十一頁(yè)，共二十六頁(yè)，編輯于2023年，星期二頂點(diǎn)結(jié)點(diǎn)：031B35189A1DDA0231B123D1firstin=?。?,0＞地址firstout=弧＜0,2＞地址data存儲(chǔ)與頂點(diǎn)有關(guān)的信息,如：名字A22第二十二頁(yè)，共二十六頁(yè)，編輯于2023年，星期二

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

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

比較無(wú)向圖的鄰接