如何將一組弧表示為鄰接矩陣和鄰接表?

如何將一組弧表示為鄰接矩陣和鄰接表?

圖的表示:弧到鄰接矩陣和鄰接表的轉換

本文演示如何將一組有向弧轉換為圖的兩種常用表示形式:鄰接矩陣和鄰接表。 我們將使用以下弧集合作為示例:?v0,v1?,?v1,v1?,?v1,v3?,?v2,v3?。 這組弧描述了一個包含四個頂點 (v0, v1, v2, v3) 的有向圖。

首先,讓我們解讀這些?。?v0,v1? 表示一條從 v0 指向 v1 的有向邊;?v1,v1? 表示 v1 頂點上的自環;?v1,v3? 表示一條從 v1 指向 v3 的有向邊;?v2,v3? 表示一條從 v2 指向 v3 的有向邊。

鄰接矩陣表示:

鄰接矩陣使用一個二維數組表示圖。數組的行和列分別對應圖中的頂點。如果從頂點 i 到頂點 j 存在一條邊,則矩陣元素 aij 為 1,否則為 0。對于加權圖,aij 可以存儲邊的權重。

基于給定的弧集合,我們可以構建一個 4×4 的鄰接矩陣:

     v0  v1  v2  v3 v0   0   1   0   0 v1   0   1   0   1 v2   0   0   0   1 v3   0   0   0   0

鄰接表表示:

鄰接表是一種更節省空間的圖表示方法,尤其對于稀疏圖。它使用一個數組,數組的每個元素都對應一個頂點,并指向一個鏈表,該鏈表存儲與該頂點相鄰的頂點。

基于給定的弧集合,對應的鄰接表如下:

v0: v1 v1: v1, v3 v2: v3 v3: 

這意味著 v0 連接到 v1;v1 連接到自身 (自環) 和 v3;v2 連接到 v3;v3 沒有出度邊。

總結:本文展示了如何將一組弧轉換為鄰接矩陣和鄰接表。這兩種表示方法各有優缺點,選擇哪種方法取決于具體的應用場景和圖的特性(例如,圖的稀疏程度)。

? 版權聲明
THE END
喜歡就支持一下吧
點贊12 分享