c++ - C++中的无向加权图数据结构

Question

我正在学习 C++，非常感谢您回答我的问题以帮助我理解基本概念。我确信我需要学习很多东西，但我需要一些建议来帮助我找到正确的方法。我遇到的问题在下面解释。

我想实现一个类来用 C++ 创建图形。正如我所注意到的，我可以使用矩阵，但我对矩阵不感兴趣，稍后您会看到。该图是无向的和加权的。该图是节点 vector ，我使用标准库 vector 。图的每个节点(顶点)都有以下参数和一些邻居。

node_index, node_degree, X, Y , Z.

邻居也是节点，我可以为它们定义一个节点 vector 。但是，我不喜欢创建节点 vector 有 3 个原因。首先，我不需要

Y,Z

来自邻居。我还需要该节点与其每个邻居之间的权重。其次，我需要分别计算每个节点的 node_degree、X，如果我有重复的节点作为邻居，我需要手动更新它们，这是额外的工作。第三，图表会很大，我不想为无用的信息浪费宝贵的内存。

话虽如此，我正在考虑拥有一个基类，稍后我可以从中派生 Node 类和 Neighbor 类。然后对于邻居，我保留一个指向每个邻居开头的指针 vector 。我不知道怎么做，但我想我可以将该指针转换为基类，并通过使用它我可以从邻居节点检索我需要的信息。

换句话说，我试图保留指向邻居的指针，当我更新邻居参数时，我直接使用指针访问节点的最新信息。

能否请您提供相关主题的链接，我应该学习如何实现它？

如果这是一个非常糟糕的主意(通过解释问题)，请告诉我什么是更好或最好的方法。

Answer 1

我建议您使用Link 结构来表示图中的边:

struct Link
{
  Node *N;
  float weight;
}

然后每个Node可以包含

vector<Link> neighbors;

这样就没有重复的节点。有一个权重重复，因为如果节点 A 有一个指向节点 B 的链接，那么节点 B 有一个指向节点 A 的相同权重的链接。如果权重重复是一个问题(例如，如果图太大权重的存储很昂贵，或者如果权重经常更新)，那么你可以使链接双向(两个 Node* 和一个权重)并给每个节点

vector<*Link>

那样的话代码会稍微复杂一些，但这是效率的代价。