轉載?圖論基礎知識（四）_Karen_Yu_的博客-CSDN博客

目錄

鄰接矩陣

百度百科的定義

解釋

代碼

鄰接表

有向圖

鄰接表逆鄰接表

---

已經介紹了圖的頂點、邊、有向圖、無向圖、度、圖的同構等知識

鏈接如下：

圖論基礎知識（一）

圖論基礎知識（二）

圖論基礎知識（三）

好了，今天想介紹的是鄰接矩陣以及鄰接表（先寫一點，之后補充）

先放一張鄰接表和鄰接矩陣對比：

鄰接矩陣

————————————同濟第六版線性代數第27頁例3——————————————

四個城市間的航線如上圖所示。

若令a ij=①? 1????? 從i市到j市有1條單向航線

??????????????②? 0???? 從i市到j市沒有單向航線

上圖所示就是一個有向圖

……

……

好了，回歸正題

百度百科的定義

鄰接?矩陣（Adjacency Matrix）是表示頂點之間相鄰關系的矩陣。設G=(V,E)是一個圖，其中V={v1,v2,…,vn} 。G的鄰接矩陣是一個具有下列性質的n階方陣：

①對?無向圖而言，鄰接矩陣一定是對稱的，而且主對角線一定為零（在此僅討論無向簡單圖），副對角線不一定為0，?有向圖則不一定如此。

②在無向圖中，任一頂點i的度為第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列非零元素個數之和。

用鄰接矩陣表示圖，很容易確定圖中任意兩個頂點是否有邊相連。

解釋

上面舉的例子是有向圖，那么，大家想想無向圖的特點是什么呢？

很簡單，也就是——i市可以到j市，同樣j市也可以到i市，所以自然而然的無向圖的鄰接矩陣一定是對稱的。

見下圖（無向圖和有向圖鄰接矩陣對比——圖片來自?數據結構：圖的存儲結構之鄰接矩陣）

————————————————簡而言之———————————————

鄰接矩陣是用一個以0和1為元素來表示頂點與頂點之間邊的關系的一種圖的表示形式

代碼

參考（來自?數據結構：圖的存儲結構之鄰接矩陣）：

#include<iostream>using?namespace?std;#define?MAXVEX?100/*?最大頂點數，應由用戶定義?*/#define?INFINITY??65535?/*?表示權值的無窮*/typedef?int?EdgeType;/*?邊上的權值類型應由用戶定義?*/typedef?char?VertexType;/*?頂點類型應由用戶定義??*/typedef?struct{VertexType?vexs[MAXVEX];/*?頂點表?*/EdgeType?arc[MAXVEX][MAXVEX];/*?鄰接矩陣，可看作邊表?*/int?numNodes,?numEdges;/*?圖中當前的頂點數和邊數??*/}?MGraph;/*?建立無向網圖的鄰接矩陣表示?*/void?CreateMGraph(MGraph?*Gp){int?i,?j,?k,?w;cout?<<?"請輸入頂點數和邊數（空格分隔）："?<<?endl;cin?>>?Gp->numNodes?>>?Gp->numEdges;cout?<<?"請輸入頂點信息（空格分隔）："?<<?endl;for?(i?=?0;?i?<?Gp->numNodes;?i++)cin?>>?Gp->vexs[i];for?(i?=?0;?i?<?Gp->numNodes;?i++){for?(j?=?0;?j?<?Gp->numNodes;?j++){if?(i?==?j)Gp->arc[i][j]?=?0;/*?頂點沒有到自己的邊*/elseGp->arc[i][j]?=?INFINITY;/*?鄰接矩陣初始化?*/}}for?(k?=?0;?k?<?Gp->numEdges;?k++){cout?<<?"請輸入邊（vi,?vj)的上標i，下標j和權值w（空格分隔）:"?<<?endl;cin?>>?i?>>?j?>>?w;Gp->arc[i][j]?=?w;Gp->arc[j][i]?=?Gp->arc[i][j];/*?因為是無向圖，矩陣對稱?*/}}int?main(void){MGraph?MG;CreateMGraph(&MG);return?0;}

還有其他的代碼展示，舉例：http://blog.csdn.net/zhangxiangdavaid/article/details/38321327

除了這種鄰接矩陣，當然還有帶權重的，比如：

所有不相連的就認為權重為正無窮，其他的就↑直接把每條路徑上的權寫上（也就不是只有0和1了——0變成了無窮，1變作權重）

鄰接表

以上圖片來自網絡

下面文字摘自百度百科（因為暫時這里還沒怎么看懂，所以以后會接著更新的）

有向圖

對于有向圖，vi的鄰接表中每個表結點都對應于以vi為始點射出的一條邊。因此，將有向圖的鄰接表稱為出邊表。

【例】有向圖G6如下圖所示，其中頂點v1的鄰接表上兩個表結點中的頂點序號分別為0和4，它們分別表示從v1射出的兩條邊(簡稱為v1的出邊)：<v1，v0>和<v1，v4>。

注意：

n個頂點e條邊的有向圖，它的鄰接表表示中有n個頂點表結點和e個邊表結點。（因為有向圖是單向的）

鄰接表逆鄰接表

在有向圖中，為圖中每個頂點vi建立一個入邊表的方法稱逆鄰接表表示法。

入邊表中的每個表結點均對應一條以vi為終點(即射入vi)的邊。

注意：

n個頂點e條邊的有向圖，它的逆鄰接表表示中有n個頂點表結點和e個邊表結點。

鄰接表是一個二維容器，第一維描述某個點，第二維描述這個點所對應的邊集們。

實現鄰接表的方法絕對有100種以上。即使是前向星這種東西也是鄰接表，因為它還是描述某個點和這個點所對應的邊集們.

我們說說常用的鄰接表存圖法（靜態的array就不說了.）必須有開O1以及以上編譯的條件，不然沒有測試的效率無任何意義。

第一維是描述點的。可以用vector,list,forward_list,deque,map,multimap,unordered_map,unordered_multimap等（一般不能用set,mutiset,unordered_set,unordered_multiset）.

按照你的要求去選擇。一般來講存完圖以后不涉及點的加入與刪除優先使用vector.map,multimap,unordered_map,unordered_multimap.

第二維是描述這個點的邊集，可以用全部的容器。?也是的一般來講存完圖以后,不涉及點的加入與刪除優先使用vector,空間充足可以考慮deque.涉及點的刪除用forward_list或者是list,map,multimap,unordered_map,unordered_multimap.

總結

以上是生活随笔為你收集整理的图论-邻接矩阵的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。