什麼是最簡單的表示圖形邊緣的方法？我是用列表的形式表示的？在C編程語言中

Question

我們如何在C編程中將圖表表示爲邊界列表？

Answer 1

如果要存儲精確的邊，請使用權重矩陣：int** M;，其中M[i][t]是i和t頂點之間的邊的長度。

如果你的圖形邊緣有重量的1，你可以圖存儲在鄰接矩陣，其中M[i][t]等於：

• 如果我和T頂點之間沒有邊
• 如果存在從i邊緣到t
• 阿爾法如果我==噸，有一個循環在I（或T）頂點

如果requre結構，關鍵的內存使用，存儲在鏈表，其中每個頂點有結構的圖表：

struct Vertex 
{ 
    int N; 
    Vertex* next; 
}; 

所以，你將有頂點結構的陣列，每個都包含指向下它連接到。例如，下面是一些鏈表-圖表：

• 1 - > 3 - > 4
• 2 - > 5
• 3 - > 4
• 4 - > 3
• 5 - > 2

Answer 2

有這樣的三種常用的方法：

1. 鄰接矩陣：一個V * V的邊權重表，其中第j行的第i列是頂點i和j之間邊的權重。如果沒有邊緣，經常使用無窮大（或者可以使用一些哨兵值，如-1）。

2. 鄰接列表：V鏈表的數組。數組中的每個第i個列表都是離開第i個頂點的邊的列表。

3. 邊緣列表：簡單的邊緣元組列表（u，v）。

不同的適用於不同的目的。我個人認爲鄰接表是最有用的，但是如果你有一個非常密集的圖，那麼鄰接矩陣可以改善性能和內存使用。

Answer 3

除非你真的想自己實現這個表示，作爲一個學習練習或者有更多的控制權，否則考慮使用一個庫，例如igraph這是一個用於表示和操作圖的C庫。或者降低一個抽象級別 - 自己創建鄰接列表或邊界列表，但使用glib的列表構建功能而不是自行編譯。