圖的表示

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

• 鄰接矩陣
• 鄰接表

鄰接矩陣

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

無向圖的鄰接矩陣

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

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

有向圖的鄰接矩陣

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

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

鄰接表

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

Mahesh Parahar

更新於: 2019年8月26日

1K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習