圖的表示:弧到鄰接矩陣和鄰接表的轉換
本文演示如何將一組有向弧轉換為圖的兩種常用表示形式:鄰接矩陣和鄰接表。 我們將使用以下弧集合作為示例:?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