在加权图的邻接矩阵中表示边缘缺失

Question

我试图在C中实现一些使用邻接矩阵作为支持数据结构的图算法。 我需要实现一个加权图，用实数表示的重量。

由于0和负数对于边是正确的权重，我怎么能表示两个节点之间没有边？

Answer 1

你可以使用，而不是一个数（double）这样的结构：

struct weight 
{ 
    double weight; 
    bool edge_exists; 
}; 

，创造weight的邻接矩阵。所以如果edge_exist s是假的，没有理由检查weight，否则weight将是有意义的。

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

Answer 2

怎么样无意义（我猜你是假设所有权重应该是正数）数字，比如-1？

这将保持代码轻便（不需要添加额外的数据结构），并且它会很容易记住。