在加權圖的鄰接矩陣中表示邊緣缺失

Question

我試圖在C中實現一些使用鄰接矩陣作爲支持數據結構的圖算法。 我需要實現一個加權圖，用實數表示的重量。

由於0和負數對於邊是正確的權重，我怎麼能表示兩個節點之間沒有邊？

Answer 1

你可以使用，而不是一個數（double）這樣的結構：

struct weight 
{ 
    double weight; 
    bool edge_exists; 
}; 

，創造weight的鄰接矩陣。所以如果edge_exist s是假的，沒有理由檢查weight，否則weight將是有意義的。

我會使用上述如果每個（？）double可能是一個可能的重量值。

Answer 2

怎麼樣無意義（我猜你是假設所有權重應該是正數）數字，比如-1？

這將保持代碼輕便（不需要添加額外的數據結構），並且它會很容易記住。