數(shù)據(jù)結(jié)構(gòu)主講人：楊丹常州信息職業(yè)技術(shù)學(xué)院5.2圖的表示和實(shí)現(xiàn)Part01鄰接矩陣設(shè)G=(V,E)是具有n個(gè)頂點(diǎn)的圖，即V={v0,v1,…，vn-1}，那么G的鄰接矩陣是元素具有如下性質(zhì)的n階方陣A，對于A中的每個(gè)元素aij，滿足：鄰接矩陣圖的鄰接矩陣表示和實(shí)現(xiàn)

圖的鄰接矩陣表示和實(shí)現(xiàn)4無向圖帶權(quán)網(wǎng)無向圖在圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)中，結(jié)點(diǎn)信息使用一維數(shù)組存儲(chǔ)，邊信息的鄰接矩陣使用二維數(shù)組存儲(chǔ)。無向圖有向圖頂點(diǎn)表鄰接矩陣有向圖圖的鄰接矩陣表示和實(shí)現(xiàn)5在圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)中，結(jié)點(diǎn)信息使用一維數(shù)組存儲(chǔ)，邊信息的鄰接矩陣使用二維數(shù)組存儲(chǔ)。無向圖帶權(quán)圖有向圖頂點(diǎn)表有向圖鄰接矩陣有向圖圖的鄰接矩陣表示和實(shí)現(xiàn)6若G是帶權(quán)圖，則鄰接矩陣可定義為：帶權(quán)圖及其鄰接矩陣無向圖帶權(quán)圖帶權(quán)圖

Part02鄰接表

對于圖G中的每個(gè)頂點(diǎn)vi，把所有鄰接于vi的頂點(diǎn)vj鏈成一個(gè)帶頭結(jié)點(diǎn)的單鏈表，這個(gè)單鏈表就稱為頂點(diǎn)vi的鄰接表。鄰接表圖的鄰接表表示和實(shí)現(xiàn)鄰接表鄰接表的結(jié)點(diǎn)結(jié)構(gòu)9表結(jié)點(diǎn)頭結(jié)點(diǎn)鄰接表中每個(gè)表結(jié)點(diǎn)均有兩個(gè)域：①鄰接點(diǎn)域dest，存放與vi相鄰接的頂點(diǎn)vj的序號j；②鏈域next，將鄰接表的所有表結(jié)點(diǎn)鏈在一起。表結(jié)點(diǎn)結(jié)構(gòu)頂點(diǎn)vi鄰接表的頭結(jié)點(diǎn)包含兩個(gè)域：①頂點(diǎn)域data，存放頂點(diǎn)vi的信息；②指針域adj，vi的鄰接表的頭指針。頭結(jié)點(diǎn)結(jié)構(gòu)圖的鄰接表表示和實(shí)現(xiàn)10無向圖無向圖對于無向圖，vi的鄰接表中每個(gè)表結(jié)點(diǎn)都對應(yīng)于與vi相關(guān)聯(lián)的一條邊。因此，將鄰接表的表頭向量稱為頂點(diǎn)表。將無向圖的鄰接表稱為邊表。有向圖無向圖及其鄰接表圖的鄰接表表示和實(shí)現(xiàn)11無向圖對于有向圖，vi的鄰接表中每個(gè)表結(jié)點(diǎn)都對應(yīng)于以vi為始點(diǎn)射出的一條邊。因此，將有向圖的鄰接表稱為出邊表。有向圖有向圖及其鄰接表有向圖Part03逆鄰接表

在有向圖中，為圖中每個(gè)頂點(diǎn)vi建立一個(gè)入邊表的方法稱逆鄰接表表示法。入邊表中的每個(gè)表結(jié)點(diǎn)均對應(yīng)一條以vi為終點(diǎn)的邊。逆鄰接表有向圖