鄰接矩陣及其性質

鄰接矩陣

鄰接矩陣用於表示圖。我們可以使用鄰接矩陣表示有向圖和無向圖。以下是鄰接矩陣的關鍵屬性。

性質

  • 鄰接矩陣A[V][V]是一個大小為V × V的二維陣列，其中V是無向圖中頂點的數量。

  • 如果Vx和Vy之間存在一條邊，則A[Vx][Vy] = 1，且A[Vy][Vx]=1，否則值為零。

  • 對於有向圖，如果Vx到Vy之間存在一條邊，則A[Vx][Vy]=1，否則值為零。

無向圖的鄰接矩陣

讓我們考慮下面的無向圖並構造其鄰接矩陣：

Adjacency undirected

上面無向圖的鄰接矩陣將是：



a
b
c
d
a
0
1
1
0
b
1
0
1
0
c
1
1
0
1
d
0
0
1
0

有向圖的鄰接矩陣

讓我們考慮下面的有向圖並構造其鄰接矩陣：

Adjacency directed

上面有向圖的鄰接矩陣將是：



a
b
c
d
a
0
1
1
0
b
0
0
1
0
c
0
0
0
1
d
0
0
0
0

更新於：2019年8月22日

2K+瀏覽量

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告
© . All rights reserved.