表示加权图邻接矩阵中的边缺失
我正在尝试用 C 语言实现一些图形算法，使用邻接矩阵作为支持数据结构。 我需要实现一个加权图，其权重由实数表示。
鉴于 0 和负数是边的正确权重，我如何表示两个节点之间不存在边？
I'm trying to implement in C some graph algorithms, using an adjacency matrix as support data structure.
I need to implement a weighted graph, with weigths represented by a real number.
Given that 0 and negative numbers would be a correct weight for an edge, how can I represent the absence of an edge between two nodes?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您可以使用如下结构代替数字 (
double)：并创建一个
权重的邻接矩阵。因此，如果edge_exists为假，则没有理由检查weight，否则weight将有意义。如果 every(?) double 可以是可能的权重值，我将使用上面的值。
You could use instead of a number (
double) a structure like this:and create an adjacency matrix of
weight's. So ifedge_exists is false there is no reason to check theweight, otherwiseweightwill be meaningful.I would use the above if every(?)
doublecould be a possible weight value.一个无意义的数字（我猜你假设所有权重都应该是正数）怎么样，例如-1？
这将使代码保持简洁（不需要添加额外的数据结构），并且很容易记住。
What about a nonsensical (I'm guessing you're making the assumption all weights should be positive) number, such as -1?
This would keep the code light (no need to add extra data structures), and it would be simple to remember.
如果您使用的是 C99 或更高版本，则可以使用在 math.h 中定义的 INFINITY 宏，并为所有不存在的边分配权重 INFINITY。
请在此处查看有关在 C 中使用无穷大的更多详细信息：如何使用 nan 和C 中的 inf？
（从技术上讲，您也可以使用 NaN，但不能保证它被定义，而且我认为在很多算法中使用无穷大效果更好）
If you are using C99 or later you can use the
INFINITYmacro defined inmath.hand assign all non existent edges a weight ofINFINITY.Look here for more details on using infinity in C: How to use nan and inf in C?
(You could also technically use NaN, but it's not guaranteed to be defined and I think using infinity works nicer in a lot a algorithms anyways)