生成树最小化连接到多个边的顶点数？

Question

是否有算法可以找到无向图的生成树,从而最大限度地减少连接到多个边的顶点数？

例如,给定一个4 x 4网格图,我们希望在左边找到一个生成树(它有7个顶点连接到多个边)而不是右边的生成树(有12个):

编辑:如果我们只考虑平面图(甚至只是网格图),这个问题会更简单吗？

Answer 1

从来没听说过。

您可以使用广度优先搜索方法，将所有未访问的顶点添加到队列中并访问队列中的下一个顶点。同时，您可以根据从连接顶点分支的可能边数将顶点及其边添加到优先级队列中。然后递归地遍历 PQ，每次都添加最佳边缘。您只需消除包含已使用顶点的任何边即可。然后检查最后一个顶点上是否有更高优先级的边，如果有，则回溯。

这是一个丑陋的概念，但在实施中可能会更糟。