有向圖 稀疏矩陣與鄰接矩陣
鄰接矩陣(Adjacency Matrix)是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是一個圖亮元,其中V={v1,v2,…,vn}?[1]?。G的鄰接矩陣是一個具有下列性質(zhì)的n階方陣:
1.對無向圖而言勤众,鄰接矩陣一定是對稱的赖临,而且主對角線一定為零(在此僅討論無向簡單圖),副對角線不一定為0爽茴,有向圖則不一定如此葬凳。
2.在無向圖中,任一頂點(diǎn)i的度為第i列(或第i行)所有非零元素的個數(shù)室奏,在有向圖中頂點(diǎn)i的出度為第i行所有非零元素的個數(shù)火焰,而入度為第i列所有非零元素的個數(shù)。
3.用鄰接矩陣法表示圖共需要n^2個空間胧沫,由于無向圖的鄰接矩陣一定具有對稱關(guān)系荐健,所以扣除對角線為零外,僅需要存儲上三角形或下三角形的數(shù)據(jù)即可琳袄,因此僅需要n(n-1)/2個空間。