0

Given an undirected connected graph with weights. w:E->{1,2,3,4,5,6,7} - meaning there is only 7 weights possible. I need to find a spanning tree using Prim's algorithm in O(n+m) and Kruskal's algorithm in O( m*a(m,n)).

I have no idea how to do this and really need some guidance about how the weights can help me in here.

4

2 回答 2

3

您可以更快地对边权重进行排序。

在 Kruskal 算法中，您不需要 O(M lg M) 排序，您只需使用计数排序（或任何其他 O(M) 算法）。所以最终的复杂度是 O(M) 用于排序和 O(Ma(m)) 用于联合查找阶段。总共是 O(Ma(m))。

对于 Prim 算法的情况。您不需要使用堆，您需要 7 个列表/队列/数组/任何东西（具有恒定时间插入和检索），每个权重一个。然后，当您正在寻找最便宜的传出边缘时，您检查这些列表之一是否为非空（来自最便宜的列表）并使用该边缘。由于 7 是一个常数，因此整个算法的运行时间为 O(M)。

于 2012-05-28T08:53:08.103 回答
2

据我了解，回答家庭作业并不受欢迎，但这可能对其他人有用，而不仅仅是你；）

普里姆：

Prim 是一种寻找最小生成树 (MST) 的算法，就像 Kruskal 一样。可视化算法的一种简单方法是在一张纸上绘制图形。然后在您选择的所有节点上创建一条可移动的线（剪切）。在下面的示例中，集合 A 将是剪切内的节点。然后选择穿过切口的最小边，即从线内部的节点到外部的节点。始终选择权重最低的边缘。添加新节点后，您移动剪切，因此它包含新添加的节点。然后重复，直到所有节点都在切口内。

该算法的简短摘要是：

  1. 创建一个集合 A，它将包含选定的顶点。它最初将包含一个由您选择的随机起始节点。
  2. 创建另一个集合 B。它最初是空的，用于标记所有选定的边。
  3. 选择一条边 E (u, v)，即从节点 u 到节点 v 的边。边 E 必须是权重最小的边，它的节点 u 在集合 A 内，而 v 不在 A 内。 (如果有几条边权重相等，则可以随机选择任何一条边）
  4. 将边 (u, v) 添加到集合 B，将 v 添加到集合 A。
  5. 重复步骤 3 和 4 直到 A = V，其中 V 是所有顶点的集合。
  6. 集合 A 和 B 现在描述你的生成树！MST 将包含 A 中的节点，B 将描述它们如何连接。

克鲁斯卡尔：

Kruskal 与 Prim 相似，只是没有剪辑。所以你总是选择最小的边。

  1. 创建一个集合 A，它最初是空的。它将用于存储选择的边缘。
  2. 从集合 E 中选择权重最小的边 E，该边不在 A 中。 (u,v) = (v,u)，因此只能沿一个方向遍历边。
  3. 将 E 添加到 A。
  4. 重复 2 和 3 直到 A 和 E 相等，也就是说，直到您选择了所有边。

我不确定这些算法的确切性能，但我假设 Kruskal 为 O(E log E) 并且 Prim 的性能取决于您用于存储边缘的数据结构。如果使用二叉堆，搜索最小边比使用邻接矩阵存储最小边要快。

希望这可以帮助！

于 2012-05-28T08:51:18.993 回答