c - 表示加权图的邻接矩阵中的边缺失

Question

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

鉴于 0 和负数将是边缘的正确权重，我如何表示两个节点之间没有边缘？

score 2 · Accepted Answer

您可以使用这样的结构来代替数字 ( double)：

struct weight
{
   double weight;
   bool edge_exists;
};

并创建一个weight's 的邻接矩阵。因此，如果edge_exists 为假，则没有理由检查weight，否则weight将是有意义的。

如果every(?)double可能是一个可能的权重值，我会使用上面的。

score 0 · Accepted Answer

一个荒谬的（我猜你假设所有的权重都应该是正的）数字，比如-1呢？

这将使代码保持简洁（无需添加额外的数据结构），并且易于记忆。

score 0 · Accepted Answer

如果您使用的是 C99 或更高版本，您可以使用中INFINITY定义的宏math.h并为所有不存在的边分配INFINITY.

在此处查看有关在 C 中使用无穷大的更多详细信息：如何在 C 中使用 nan 和 inf？

（从技术上讲，您也可以使用 NaN，但不能保证定义它，而且我认为在很多算法中使用无穷大效果更好）

3 回答 3