圖形表示法

圖形表示法有四種，以下會逐一介紹

• 相鄰矩陣 (Adjacency Matrix)
• 相鄰串列 (Adjacency List)
• 相鄰多元串列 (Adjacency Multilist)
• 索引表 (Index Table)

相鄰矩陣 (Adjacency Matrix)

• 鄰接矩陣是一個二維矩陣，其中的行和列分別對應圖中的頂點。
• 矩陣的元素表示頂點之間的邊的存在或權重。如果兩個頂點相鄰，則矩陣元素為1（或邊的權重值），否則為0（或無限大）。
• 適用於稠密圖，因為矩陣大小為n x n，其中n是頂點數。

優點

• 快速查詢兩個頂點之間是否有邊，時間複雜度為O(1)。
• 適用於稠密圖，因為它只需要記錄存在的邊。

缺點

• 佔用大量內存空間，對於大型圖來說可能會造成浪費。
• 不適用於疏鬆圖，因為大部分元素都是0，浪費空間。
• 不容易表示有向圖中的多重邊或帶權重的圖。

適用時機

• 當需要快速查詢是否有邊或處理稠密圖時。
• 對於小型圖或密集連接的圖效果較好。

相鄰列表（Adjacency List）

• 鄰接列表使用鏈表或數組來表示每個頂點的鄰接頂點。
• 每個頂點都有一個相關聯的鄰接列表，其中包含與該頂點相鄰的頂點。
• 適用於疏鬆圖，因為只存儲實際存在的邊。

優點

• 節省記憶體，只存儲實際存在的邊，對於疏鬆圖節省空間。
• 易於遍歷一個頂點的鄰接頂點。
• 適用於表示有向圖、多重邊和帶權重的圖。

缺點

查詢兩個頂點之間是否有邊的時間複雜度為O(deg(V))，其中deg(V)是一個頂點的度數。

適用時機

• 當處理疏鬆圖、有向圖、多重邊或帶權重的圖時。
• 當記憶體使用需求較低並且不需要快速查詢是否有邊時。

相鄰多元列表（Adjacency Multilist）

• 相鄰多元列表是一種擴展的鄰接列表，用於表示有向圖和具有多重邊的圖。除了存儲鄰接頂點外，它還記錄了多重邊的信息，以及邊的權重等其他屬性。
• 這種表示方式適用於複雜的圖結構，但可能需要更多的存儲空間和複雜的查詢操作。

優點：

• 能夠表示有向圖中的多重邊和帶權重的圖。
• 提供更豐富的邊信息。

缺點

• 需要更多的記憶體空間。
• 查詢和更新較複雜，需要額外的操作。

適用時機

當需要準確表示多重邊、帶權重或具有複雜邊屬性的圖。

索引表（Index Table）

索引表是一種簡單的表示方法，它使用頂點的索引來描述圖中的邊。對於每條邊，它存儲相關聯的頂點的索引或標識符。
這種表示方式可以用於節省內存空間，但可能需要額外的數據結構來實現圖形操作。

優點

• 簡單、節省記憶體。
• 可以用於較小的圖。

缺點

不提供直接的鄰接頂點信息，需要進一步查找。

適用時機

當處理較小的圖或僅需簡單表示時。