在加权图中查找边缘

我有一个包含四个节点的图，每个节点代表一个位置，它们像二维网格一样布局。每个节点都有一个连接（边缘）给所有（根据位置）相邻的节点。每条边都有一个重量。在加权图中查找边缘

下面是由A，B，C，d和边缘的权重表示由数字指示的节点：

欲结构的容器和用于切换节点共享的算法最重的边缘。然后重置该边的重量。每次执行算法时，节点（位置）都不能切换一次以上。

例如，处理上面的，最高的权重是边缘BD，所以我们切换这些。由于没有节点可以多次切换，因此B或D中涉及的所有边都将被重置。

然后，下一个最高权重是唯一的边缘左侧，切换这些会给我们最终布局：C，d，A，B。

我目前正在运行一个相当可怕的实现。我存储一长串边缘，它们（可能）连接的节点持有四个值，其重量值和节点本身的位置。每次请求时，我都会循环整个列表。

我正在用C++写这篇文章，STL的某些部分可以帮助加快速度吗？另外，如何避免重复数据？节点位置当前在五个对象中。该节点本身和四个节点表示与它的连接。

总之，我想帮助：

可以这样的方式来构造，使得没有数据重复？
意识到这个问题？如果有任何这样的名字，告诉我，我可以谷歌的主题更多的信息。
快速算法总是很好。

来源

2009-07-24 Mizipzor

假设边缘仅在网格位置之间正交连接，网格本身是正方形，则边缘的数量可以由2n（n + 1）给出，其中n = sizex-1 = sizey-1 ...如果它帮助。来源：http：//www.research.att.com/~njas/sequences/A046092 – Mizipzor 2009-07-24 21:10:02

至于名称，这是一个顶点覆盖问题。最佳顶点覆盖是具有可靠的近似解决方案的NP难度，但您的问题更简单。您正在严格的边缘选择标准下查看伪最大值。具体来说，一旦选择了一条边，每一条连接的边被移除（表示要移除要交换的顶点）。

例如，下面是一个标准的贪婪方法：

0）的边缘进行排序;保留邻接信息
而边缘保持：
1）选择最高边缘
2）从列表中删除所有相邻边缘
ENDWHILE

选定边的列表给出了顶点交换。
时间复杂度为O（排列顶点+顶点上的线性通道），通常会归结为O（排序顶点），这可能由O（V * log（V））决定。

保留邻接信息的方法取决于图属性;看到你友好的本地算法文本。为了简单起见，可以从一个邻接矩阵开始。

与邻接信息一样，大多数其他速度改进将最适用于某种形状的图形，但具有时间与空间复杂度的权衡。

例如，您的问题陈述似乎意味着顶点以正方形模式布局，从中可以派生出许多有趣的属性。例如，该系统非常容易并行化。此外，邻接信息将是高度规则的，但在大图大小时稀疏（大多数顶点不会相互连接）。这使得邻接矩阵给出了很高的开销;您可以将邻接存储在4元组数组中，因为它可以保持快速访问，但几乎可以完全消除开销。

来源

2009-07-24 21:28:13

“边缘着色为每个边缘指定一种颜色，使得没有两个相邻边缘共享相同的颜色”（http：//en.wikipedia。组织/维基/ Graph_coloring）。对我来说就像我只对两种“颜色”感兴趣，处理和不处理。 “相邻边缘不共用颜色”问题应该以什么方式考虑？ – Mizipzor 2009-07-24 21:39:43

如果您有更大的图表，请查看boost graph库。它为您提供了良好的图形和基本迭代器的数据结构，用于不同类型的图遍历

来源

2009-07-24 21:16:14 Janusz

在加权图中查找边缘

回答

相关问题