數(shù)據(jù)結(jié)構(gòu)-基于C++語(yǔ)言（微課版） 課件 4-鄰接表

本節(jié)內(nèi)容：鄰接表圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)鄰接表：對(duì)于無(wú)向圖，把依附于同一個(gè)頂點(diǎn)的邊鏈接在同一個(gè)單鏈表中稱為邊鏈表，邊鏈表中的每一個(gè)結(jié)點(diǎn)代表一條邊叫做邊結(jié)點(diǎn)。邊結(jié)點(diǎn)存放與該邊相關(guān)聯(lián)的另一個(gè)結(jié)點(diǎn)的序號(hào)和指向下一個(gè)邊結(jié)點(diǎn)的指針。對(duì)于有向圖，把從同一個(gè)頂點(diǎn)出發(fā)的弧鏈接在同一個(gè)單鏈表中稱為弧鏈表，弧鏈表中的每一個(gè)結(jié)點(diǎn)代表一條弧叫做弧結(jié)點(diǎn)。弧結(jié)點(diǎn)存放該弧的弧頭頂點(diǎn)序號(hào)和指向下一個(gè)弧結(jié)點(diǎn)的指針。圖中的每一個(gè)頂點(diǎn)用一個(gè)結(jié)點(diǎn)表示，稱為頂點(diǎn)結(jié)點(diǎn)。圖的存儲(chǔ)結(jié)構(gòu)無(wú)向圖的鄰接表datafirstarc1013^adjvexnextarc01234324^0^4^212^aecbdG1無(wú)向圖acdbe頂點(diǎn)結(jié)點(diǎn)邊結(jié)點(diǎn)特點(diǎn)：對(duì)于無(wú)向圖的鄰接表，同一條邊在鄰接表中出現(xiàn)了兩次，頂點(diǎn)Vi的度是頂點(diǎn)Vi的邊鏈表中的邊結(jié)點(diǎn)的個(gè)數(shù)。圖的存儲(chǔ)結(jié)構(gòu)有向圖的鄰接表G2有向圖bdac特點(diǎn)：對(duì)于有向圖的鄰接表，頂點(diǎn)Vi的出度是頂點(diǎn)Vi的弧鏈表中的弧結(jié)點(diǎn)的個(gè)數(shù)?；〗Y(jié)點(diǎn)12^3^firstarc頂點(diǎn)結(jié)點(diǎn)0123acdbdata^0^adjvex

nextarc圖的存儲(chǔ)結(jié)構(gòu)有向圖的逆鄰接表頂點(diǎn)Vi的弧鏈表中鏈接的是所有進(jìn)入該頂點(diǎn)的弧。特點(diǎn)：在有向圖逆鄰接表中，頂點(diǎn)Vi的入度是頂點(diǎn)Vi的弧鏈表中的弧結(jié)點(diǎn)個(gè)數(shù).G2無(wú)向圖bdac0123acdbdatafirstarc0^0^2^3adjvex

nextarc^逆鄰接表圖的存儲(chǔ)結(jié)構(gòu)小結(jié)：若圖G中有n個(gè)頂點(diǎn)和e條邊，則：用鄰接表表示無(wú)向圖時(shí)，需要n個(gè)頂點(diǎn)結(jié)點(diǎn)和2e個(gè)邊結(jié)點(diǎn)。頂點(diǎn)Vi的度是頂點(diǎn)Vi的邊鏈表中的邊結(jié)點(diǎn)的個(gè)數(shù)。用鄰接表表示有向圖時(shí)，若不考慮逆鄰接表，需要n個(gè)頂點(diǎn)結(jié)點(diǎn)和e個(gè)弧結(jié)點(diǎn)。頂點(diǎn)Vi的出度是頂