2018年國(guó)家電網(wǎng)考試備考計(jì)算機(jī)之?dāng)?shù)據(jù)結(jié)構(gòu)與算法(10)

1.1 鄰接矩陣

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

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

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

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

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

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

(2)要知道某個(gè)頂點(diǎn)的度，其實(shí)就是這個(gè)頂點(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個(gè)頂點(diǎn)，則鄰接矩陣是一個(gè)n*n的方陣，定義為：

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

。

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