在加权图中求边

我有一个有四个节点的图,每个节点代表一个位置,它们被布置成二维网格。每个节点都有一个连接(边)到所有(根据位置)相邻节点。每边都有重量。

以下是由a、b、c、d表示的节点,边缘的重量由数字表示:

A     100     B

120         220

C     150     D

我想构造一个容器和一个算法,它可以切换共享最大权重边缘的节点。然后重置该边的权重。每次执行算法时,节点(位置)都不能切换一次以上。

例如,处理上面的内容时,最大的权重在edge bd上,所以我们切换它们。由于没有节点可以多次切换,因此B或D中涉及的所有边都将被重置。

A             D

120         

C             B

然后,下一个最大的重量是在唯一的左边,切换这些将给我们最终的布局:C,D,A,B。

我目前正在运行一个非常糟糕的实现。我存储了一个很长的边列表,其中包含它们(可能)连接到的节点的四个值、其权重值和节点本身的位置。每次有任何请求时,我都会循环查看整个列表。

我是用C++写的,STL的某些部分有助于加快速度吗?另外,如何避免重复数据?节点位置当前位于五个对象中。存在的节点本身以及四个节点,指示与它的连接。

简言之,我需要以下方面的帮助:

• 这样的结构是否可以避免重复数据?
• 认识到问题了吗?如果其中任何一个有名字,告诉我,这样我就可以在谷歌上搜索更多关于这个主题的信息。
• 快速算法总是很好的。