| 語言 : |
|
| 百科社區 |百科問答 |提交問題 |詞彙知識 |上傳知識 |
鄰接矩陣 |
  |
|
邏輯結構分為兩部分：V和E的集合。因此，用一個一維數組存放圖中所有頂點數據；用一個二維數組存放頂點間關係（邊或弧）的數據，這個二維數組稱為鄰接矩陣。鄰接矩陣又分為有向圖鄰接矩陣和無向圖鄰接矩陣。 定義 鄰接矩陣（Adjacency Matrix）：是表示頂點之間相鄰關係的矩陣。設G=(V,E)是一個圖，其中V={v1,v2,…,vn}。 G的鄰接矩陣是一個具有下列性質的n階方陣：①對無向圖而言，鄰接矩陣一定是對稱的，而且對角線一定為零（在此僅討論無向簡單圖），有向圖則不一定如此。 ②在無向圖中，任一頂點i的度為第i列所有元素的和，在有向圖中頂點i的出度為第i行所有元素的和，而入度為第i列所有元素的和。 ③用鄰接矩陣法表示圖共需要n^2個空間，由於無向圖的鄰接矩陣一定具有對稱關係，所以扣除對角線為零外，僅需要存儲上三角形或下三角形的數據即可，因此僅需要n（n-1）/2個空間。 特點 無向圖的鄰接矩陣一定是對稱的，而有向圖的鄰接矩陣不一定對稱。因此，用鄰接矩陣來表示一個具有n個頂點的有向圖時需要n^2個單元來存儲鄰接矩陣；對有n個頂點的無向圖則只存入上（下）三角陣中剔除了左上右下對角線上的0元素後剩餘的元素，故只需1 2 ... (n-1)=n(n-1)/2個單元。 無向圖鄰接矩陣的第i行（或第i列）非零元素的個數正好是第i個頂點的度。 有向圖鄰接矩陣中第i行非零元素的個數為第i個頂點的出度，第i列非零元素的個數為第i個頂點的入度，第i個頂點的度為第i行與第i列非零元素個數之和。 用鄰接矩陣表示圖，很容易確定圖中任意兩個頂點是否有邊相連。 描述 用一個順序表來存儲頂點信息 int i，j，k，w; scanf("%d%d"，&G->n，&G->e); //輸入頂點數和邊數 for(i = 0;i < n;i ) //讀人頂點信息，建立頂點表 { G->vexs=getchar(); } for(i = 0;i < G->n;i ) { for(j = 0;j < G->n;j ) { G->edges[i][j] = 0; //鄰接矩陣初始化 } } for(k = 0;k < G->e;k ) {//讀入e條邊，建立鄰接矩陣 scanf("%d%d%d"，&i，&j，&w); //輸入邊(vi ,vj )上的權w G->edges[i][j]=w; |
| 用戶 評論 |
|
還沒有評論 |
