1.1 鄰接矩陣

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

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

看一個實例，下圖左就是一個無向圖。

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

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

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

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

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

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

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

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

。

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