圖的表示

主要有兩種方法來表示圖：

  • 鄰接矩陣
  • 鄰接表

鄰接矩陣

鄰接矩陣 A[V][V] 是一個大小為 V × V 的二維陣列，其中 $V$ 是無向圖中頂點的數量。如果在 Vx 和 Vy 之間存在一條邊，則 A[Vx][Vy]=1 且 A[Vy][Vx]=1，否則值為零。對於有向圖，如果在 Vx 和 Vy 之間存在一條邊，則 A[Vx][Vy]=1，否則值為零。

無向圖的鄰接矩陣

讓我們考慮以下無向圖並構建其鄰接矩陣：

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



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

有向圖的鄰接矩陣

讓我們考慮以下有向圖並構建其鄰接矩陣：

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



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

鄰接表

在鄰接表中，一個連結列表的陣列 (A[V]) 用於表示具有 V 個頂點的圖 G。條目 A[Vx] 表示與第 Vx 個頂點相鄰的頂點的連結列表。無向圖的鄰接表如下所示：


更新於: 2019年8月26日

1K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告