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