1.1 鄰接矩陣

圖的鄰接矩陣存儲方式是用兩個數(shù)組來表示圖。一個一維數(shù)組存儲圖中頂點(diǎn)信息，一個二維數(shù)組(鄰接矩陣)存儲圖中的邊或弧的信息。

設(shè)圖G有n個頂點(diǎn)，則鄰接矩陣是一個n*n的方陣，定義為：

看一個實(shí)例，下圖左就是一個無向圖。

從上面可以看出，無向圖的邊數(shù)組是一個對稱矩陣。所謂對稱矩陣就是n階矩陣的元滿足aij = aji。即從矩陣的左上角到右下角的主對角線為軸，右上角的元和左下角相對應(yīng)的元全都是相等的。

從這個矩陣中，很容易知道圖中的信息。

(1)要判斷任意兩頂點(diǎn)是否有邊無邊就很容易了;

(2)要知道某個頂點(diǎn)的度，其實(shí)就是這個頂點(diǎn)vi在鄰接矩陣中第i行或(第i列)的元素之和;

(3)求頂點(diǎn)vi的所有鄰接點(diǎn)就是將矩陣中第i行元素掃描一遍，arc[i][j]為1就是鄰接點(diǎn);

而有向圖講究入度和出度，頂點(diǎn)vi的入度為1，正好是第i列各數(shù)之和。頂點(diǎn)vi的出度為2，即第i行的各數(shù)之和。

若圖G是網(wǎng)圖，有n個頂點(diǎn)，則鄰接矩陣是一個n*n的方陣，定義為：

這里的wij表示(vi,vj)上的權(quán)值。無窮大表示一個計算機(jī)允許的、大于所有邊上權(quán)值的值，也就是一個不可能的極限值。下面左圖就是一個有向網(wǎng)圖，右圖就是它的鄰接矩陣

。

那么鄰接矩陣是如何實(shí)現(xiàn)圖的創(chuàng)建的呢?代碼如下。