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

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

本文演示如何將一組有向弧轉換為圖的兩種常用表示形式：鄰接矩陣和鄰接表。 我們將使用以下弧集合作為示例：?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 存在一條邊，則矩陣元素 a_ij 為 1，否則為 0。對于加權圖，a_ij 可以存儲邊的權重。

基于給定的弧集合，我們可以構建一個 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 沒有出度邊。

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