#僅供學(xué)習(xí)

線性表中數(shù)據(jù)元素是一對(duì)一關(guān)系；樹形結(jié)構(gòu)中數(shù)據(jù)元素是一對(duì)多的關(guān)系；圖形結(jié)構(gòu)是多對(duì)多關(guān)系。

基本概念

圖的存儲(chǔ)

圖的結(jié)構(gòu)比較復(fù)雜，任何兩個(gè)頂點(diǎn)之間都可能有關(guān)系。

1）如果采用順序存儲(chǔ)，則需要使用二維數(shù)組表示元素之間的關(guān)系，即鄰接矩陣，也可以使用邊集數(shù)組，把每條邊順序存儲(chǔ)起來；

2）如果采用鏈?zhǔn)酱鎯?chǔ)，則有鄰接表，十字鏈表和鄰接多重表表示方法。

還有一種是算法競賽時(shí)經(jīng)常使用的方法，鏈?zhǔn)角跋蛐?，它是鄰接表和邊集?shù)組的結(jié)合。

其中，鄰接矩陣和鄰接表是最簡單，最常用的存儲(chǔ)方法。

1. 鄰接矩陣：

????（1）無向圖的鄰接矩陣

（2）有向圖的鄰接矩陣

（3）網(wǎng)的鄰接矩陣

????????鄰接矩陣的數(shù)據(jù)結(jié)構(gòu)

2. 鄰接表：

????鄰接表（Adjacency List）是圖的一種鏈?zhǔn)酱鎯?chǔ)的方法。鄰接表包含兩部分，頂點(diǎn)和鄰接點(diǎn)。頂點(diǎn)包括定點(diǎn)信息和指向第一個(gè)鄰接點(diǎn)的指針，鄰接點(diǎn)是包括鄰接點(diǎn)的存儲(chǔ)下標(biāo)和指向下一個(gè)鄰接點(diǎn)的指針。頂點(diǎn)vi的所有鄰接點(diǎn)構(gòu)成一個(gè)單鏈表。

????????鄰接表用到2個(gè)數(shù)據(jù)結(jié)構(gòu)：

????????1) 頂點(diǎn)節(jié)點(diǎn)，包括頂點(diǎn)信息和指向第一個(gè)鄰接的指針，可用一維數(shù)組存儲(chǔ)。

????????2）鄰接點(diǎn)節(jié)點(diǎn)，包括鄰接點(diǎn)的存儲(chǔ)下標(biāo)和指向下一個(gè)鄰接點(diǎn)的指針。頂點(diǎn)vi的所有鄰接點(diǎn)構(gòu)成一個(gè)單鏈表。

????????

3. 邊集數(shù)組

創(chuàng)建一個(gè)數(shù)組，每輸入一條邊，把這條邊存儲(chǔ)在數(shù)組里；

每條邊存儲(chǔ)邊的兩個(gè)頂點(diǎn)u，v,和權(quán)重w.

4. 鏈?zhǔn)角跋蛐?/strong>