圖圖的表示法

圖圖的表示法第一頁，共二十六頁，2022年，8月28日圖的基本概念及基本術語圖的表示法圖的遍歷最小生成樹最短路徑拓撲排序主要內容第二頁，共二十六頁，2022年，8月28日27.2圖的存儲結構鄰接矩陣表示法鄰接表表示法鄰接多重表十字鏈表第三頁，共二十六頁，2022年，8月28日3設圖A=(V,E)是一個有n個頂點的圖,圖的鄰接矩陣是一個二維數(shù)組A

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

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

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

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

53

62

83

2(出邊表)(頂點表)有向網(帶權圖)的鄰接表1

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

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

十字鏈表1.“圖例”后回并練習2.形式化定義與算法作圖方法：1.先畫出頂點結點（數(shù)組形式）2.畫出所有弧結點（剛弧尾將各弧結點放置在對應的頂點結點后面）3.連線第二十三頁，共二十六頁，2022年，8月28日23是有向圖的一種鏈式存儲結點結構優(yōu)點：計算出度、入度十分方便缺點：結構較復雜十字鏈表表示法第二十四頁，共二十六頁，2022年，8月28日24

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

比較無向圖的鄰接