圖的存儲(chǔ)結(jié)構(gòu)相比線性表和樹(shù)更加復(fù)雜：
- 圖中頂點(diǎn)沒(méi)有次序之分
- 圖中邊和頂點(diǎn)的數(shù)量任意
圖的存儲(chǔ)結(jié)構(gòu)可以分為兩大類：
- 鄰接矩陣（順序存儲(chǔ)）
- 鄰接表（鏈?zhǔn)酱鎯?chǔ)）：
- 十字鏈表（有向圖）
- 鄰接多重表（無(wú)向圖）
鄰接矩陣 無(wú)向圖
頂點(diǎn)：用一維數(shù)組存儲(chǔ)
邊或弧：用二維數(shù)組存儲(chǔ)
鄰接矩陣
頂點(diǎn)數(shù)組：A B C D
邊或?。?br>
A B C D
A 0 1 1 1
B 1 0 1 0
C 1 1 0 1
D 1 0 1 0
行或列中 1 的個(gè)數(shù)為頂點(diǎn)的度。
無(wú)向圖的鄰接矩陣是一個(gè)對(duì)稱矩陣。也可以只存儲(chǔ)一半矩陣以節(jié)省存儲(chǔ)空間。
鄰接矩陣 有向圖
與無(wú)向圖的區(qū)別為邊是有方向的
A B C D
A 0 1 0 1
B 0 0 1 0
C 1 1 0 1
D 0 0 0 0
從為行，到為列。
鄰接表
定點(diǎn)表：存儲(chǔ)頂點(diǎn)和第一個(gè)鄰接點(diǎn)的指針。
邊表：每個(gè)頂點(diǎn)所有鄰接的頂點(diǎn)集。
