tree - 图论，随机顶点连接以创建最大树

我正在寻找正确方向的点或解决此问题的可能算法。

我有一个连接了一些顶点的图。选择任何尚未完全连接的随机顶点，选择一条要连接的边，以创建或创建最大的树。（称之为运行。）“走向创造”意味着最小化预期创建最大树的运行次数。

此图像有两个可能的运行示例。第一次运行很简单，因为它只是选择边连接到图中唯一的树。第二次运行选择向上的边缘，因为它比选择底部边缘更靠近树。

在其他情况下，图上可能已经存在多棵树。选择的边仍应遵循尝试以最少的运行次数创建最大树的原则。

我一直在研究忽略权重的最小生成树，但我仍然遇到一些困难。我无法理解的部分是随机顶点，每次运行都是贪婪的。

标签： treegraph-theory