algorithm - 根据特定条件创建图表

Question

我有一个问题要求我制作一个图，使得图中的 BFS 和 DFS 树不是最小生成树并且邻接列表的顺序无关紧要，我知道 BFS DFS 和 MST 的属性但我对这个问题感到困惑。我应该如何解决这个问题？ (不是寻找解决方案)

Answer 1

想象一个包含 k 个顶点的完整图。对于 k > 3，DFS 树看起来总是与 BFS 树不同。对于k > 4，您可以拥有一个不同于BFS 和DFS 树的MST。您可以选择 MST 的形状，使其不同于 DFS 树，方法是确保一个顶点需要三个边。您可以选择 MST 的形状，使其不同于 BFS 树，方法是确保没有顶点有超过三个边。您可以通过分配权重来选择 MST 的形状，使您选择的边成为 MST 的一部分。

DFS Tree

1-----2----3
           |
           |
     4-----5

BFS Tree

      1
  ____|____
 /   / \   \
2   3   4   5

MST

2
|
1---3---5
|
4

五个顶点的完整图有 5 * 4/2 = 10 条边，任何树只需要其中的 4 条边。