鄰接矩陣:
使用兩個數(shù)組來存儲數(shù)據(jù)元素(頂點(diǎn))和數(shù)據(jù)元素之間的關(guān)系(邊或晃跏獭)的信息啸罢。
一維數(shù)組:用于存儲頂點(diǎn)忍啤。
二維數(shù)組:用于存儲弧或邊加勤。
鄰接矩陣的優(yōu)點(diǎn):
訪問速度快,方便計算結(jié)點(diǎn)的度同波、入度鳄梅、出度。
鄰接矩陣的缺點(diǎn):
頂點(diǎn)的容量有限未檩,擴(kuò)容非常麻煩戴尸,只適合存儲稠密圖,存儲稀疏圖時會有大量的內(nèi)存浪費(fèi)冤狡。
鄰接表:
采用一維數(shù)組加單向鏈表的方式存儲存儲孙蒙。
一維數(shù)組:用于存儲頂點(diǎn)和單向鏈表的頭指針。
單向鏈表:存儲著從該頂點(diǎn)出發(fā)的弧或邊悲雳。
鄰接表優(yōu)點(diǎn):
與鄰接矩陣相比挎峦,它可以節(jié)約內(nèi)存,有多少條邊或弧就創(chuàng)建多少個鏈表節(jié)點(diǎn)合瓢,比較適合存儲稀疏圖坦胶。
鄰接表缺點(diǎn):
計算入度、刪除節(jié)點(diǎn)時比較麻煩晴楔。
十字鏈表:
采用一維數(shù)組加兩個十字鏈表進(jìn)行存儲顿苇,之所以叫十字鏈表,是因?yàn)樗逆湵砘」?jié)點(diǎn)會被兩個鏈表指向税弃,同時弧節(jié)點(diǎn)有兩個指針纪岁,指向后續(xù)的弧節(jié)點(diǎn)。
一維數(shù)組:存儲了頂點(diǎn)數(shù)據(jù)则果,兩個鏈表頭指針蜂科。
出度鏈表:指向的是以該結(jié)點(diǎn)作為弧尾的弧節(jié)點(diǎn)顽决。
入度鏈表:指向的是以該結(jié)點(diǎn)作為弧頭的弧節(jié)點(diǎn)。
十字鏈表的優(yōu)點(diǎn):
與鄰接矩陣相比导匣,它更節(jié)約內(nèi)存才菠,與鄰接表相比它更方便計算頂點(diǎn)的出度。
十字鏈表的缺點(diǎn):
刪除頂點(diǎn)和刪除弧時比較麻煩贡定,也可以表示與實(shí)現(xiàn)無向圖赋访,但更合適表示與實(shí)現(xiàn)有向圖。