有向圖 稀疏矩陣與鄰接矩陣
鄰接矩陣（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個空間。
