資訊專欄INFORMATION COLUMN
摘要：圖關聯矩陣在關聯矩陣表示的圖中，矩陣的行表示頂點，列表示邊。如圖，頂點數是，邊的數量是，用鄰接矩陣表示圖需要的空間是，而使用關聯矩陣表示圖需要的空間是。廣度優先搜索算法數據結構是隊列。深度優先搜索算法數據結構是棧。
定義
圖和散列表、二叉樹一樣，是一種非線性數據結構。如圖1所示，圖由一系列頂點以及連接頂點的邊構成。由一條邊連接在一起的頂點成為相鄰頂點，比如A和B、A和D是相鄰的，而A和E不是相鄰的。一個頂點相鄰頂點的數量叫作度，比如A的度為3、D的度為4。路徑指相鄰頂點的一個連續序列，如ABEI、ACDG；簡單路徑指不包含重復頂點的路徑（除環外），如ADG；環指首尾頂點相同的路徑，如ADCA，環也屬于簡單路徑。如果圖中每兩個頂點之間都有路徑相連，則稱該圖是連通的。
如圖2，如果圖中的邊具有方向，稱該圖為有向圖。如果圖中的邊是雙向的，則該圖是強連通的，例如圖3中的C和D是強連通的。圖也可以是加權的，例如圖3中的每條邊都有權值。
圖可以用來解決計算機中的很多問題，比如搜索圖中的一個特定頂點或搜索一條特定邊，尋找圖中的一條路徑（從一個頂點到另一個頂點） ，尋找兩個頂點之間的最短路徑，以及環檢測。
圖的表示圖的表示方式有多種，沒有絕對正確的表示方式，采用哪種方式取決于圖的類型和待解決的問題。這里介紹三種方式：鄰接矩陣、鄰接表、關聯矩陣。
鄰接矩陣鄰接矩陣用一個二維數組來表示圖中頂點的連接情況；如果索引為i的節點和索引為j的節點連接，則array[i][j] === 1，否則array[i][j] === 0，如圖4。鄰接矩陣的缺點是，如果圖不是強連通的，矩陣中就會出現很多0，從而計算機需要浪費存儲空間來表示根本不存在的邊。例如，即使某一頂點只有一個相鄰頂點，也需要一整行來表示該頂點的連接情況，
鄰接表由圖中每個頂點的相鄰頂點的列表所組成，如圖5。只要能表示一對多的數據結構，都可以用來描述鄰接表，比如多維列表（數組）、鏈表、散列表、字典等。
在大多數情況下，鄰接表是更好的選擇，但鄰接矩陣也有其優點，比如要判斷頂點A和B是否相鄰，鄰接矩陣比鄰接表要快。
圖5
關聯矩陣在關聯矩陣表示的圖中，矩陣的行表示頂點，列表示邊。如圖6所示，我們使用二維數組來表示兩者之間的連通性，如果頂點A是邊E的入射點，則array[A][E] === 1；否則，array[A][E] === 0。
關聯矩陣通常用于邊的數量比頂點少的情況下，以節省空間和內存。如圖6，頂點數是5，邊的數量是6，用鄰接矩陣表示圖需要的空間是5*5=25，而使用關聯矩陣表示圖需要的空間是5*6=30。
圖6
創建圖類首先首先聲明類的骨架：
function Graph() {
var vertices = [];
var adjList = new Dictionary();
}
其中Dictionary類的實現參考之前的文章字典。
我們使用數組 vertices 來存儲圖中所有頂點的名字，以及字典 adjList 來存儲鄰接表。字典將會使用頂點的名字作為鍵，鄰接頂點列表作為值。
接下來實現向圖中添加頂點的方法：
this.addVertex = function(v){
vertices.push(v);
adjList.set(v, []);
};
該方法接受頂點 v 作為參數。我們將該頂點添加到頂點列表 vertices 中，并且在鄰接表中，設置頂點 v 作為鍵對應的字典值為一個空數組。
接著實現一個點到另一個點的連接：
this.addEdge = function(v, w){
adjList.get(v).push(w);
adjList.get(w).push(v);
};
這個方法接受兩個頂點作為參數。首先，我們通過將 w 加入到 v 的鄰接表中，添加了一條自頂
點 v 到頂點 w 的邊。如果是有向圖，則只需要該方法的第一行代碼就行了。我們這里要實現無向圖，我們需要添加一條自 w 向 v 的邊，即該方法的第二行代碼。
使用該圖類進行簡單的測試：
