我正在用C++实现一个图类的邻接列表(但这有点无关紧要(。我有一个加权无方向图，我正在编写addVertex方法。我基本上把所有的东西都记下来了，但我不确定当我在另外两个已经存在并有自己相应权重的顶点之间添加一个顶点时应该怎么做。
我应该扔掉顶点存储的旧权重吗？我应该使用传入的新的吗？两者兼而有之？或者我选什么根本不重要？
我只是想确保我没有做我不该做的事。
谢谢！
我想这取决于你想要实现什么。通常，邻接列表是一个嵌套列表，其中每行i指示第i个节点的邻域。确切地说，第i个节点邻域中的每个条目表示从节点i到j的传出连接。邻接列表不包括边或弧权重。
因此，添加顶点n不应影响现有邻接列表的条目，而是将新的空行n添加到邻接列表。但是，添加或删除边会更改相邻列表的条目。因此，添加一个顶点n">在已经存在并且具有它们自己的对应权重的另外两个[节点i和j]之间"；意味着删除i和j之间的现有连接，并最终添加两个新连接(i，n(和(n，j(。如果边上没有容量限制，并且距离(i，n(和(n，j(之和支配距离(i，j(，这可能是好的。但是，如果权重表示容量(例如最大流量问题(，则应保留两个连接。
所以你的问题似乎是不完整的，或者至少是不准确的。我假设您的目标是计算无向图中每对节点之间的最短距离。我建议在你的图表中保留所有不同的连接。最短路径算法可以在完成图形创建后计算每个节点对之间的最短连接。