熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構之鄰接矩陣表示法

2013-11-15 15:40:08  來源: 數據結構 

定義

  鄰接矩陣(Adjacency Matrix)是表示頂點之間相鄰關系的矩陣設G=(VE)是一個圖其中V={vvvn}G的鄰接矩陣是一個具有下列性質的n階方陣 


 
特點

  無向圖的鄰接矩陣一定是對稱的而有向圖的鄰接矩陣不一定對稱因此用鄰接矩陣來表示一個具有n個頂點的有向圖時需要n個單元來存儲鄰接矩陣對有n個頂點的無向圖則只存入上(下)三角陣故只需n(n+)/個單元
  無向圖鄰接矩陣的第i行(或第i列)非零元素的個數正好是第i個頂點的度
  有向圖鄰接矩陣中第i行非零元素的個數為第i個頂點的出度第i列非零元素的個數為第i個頂點的入度第i個頂點的度為第i行與第i列非零元素個數之和
  用鄰接矩陣表示圖很容易確定圖中任意兩個頂點是否有邊相連
 
鄰接矩陣的C語言描述

  用一個順序表來存儲頂點信息



From:http://tw.wingwit.com/Article/program/sjjg/201311/23768.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.