5

所以我需要一些帮助来找到一个最小生成树。假设我有邻接列表形式的图表：

A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35

第一个字母表示您正在查看哪个节点，数字表示与任何其他节点的连接数。例如，A 有两个连接 - B 和 I 各有一个。之后，字母后面的数字只是表示边的权重。B 的权重为 12，我的权重为 25。所以我最初计划将整个事物表示为一个名为 的字符串数组Graph[8]。每行将是阵列中的不同插槽。我很难弄清楚如何使用 Prims 或 Kruskalls 算法来实现这一点。

4

2 回答 2

6

这不是对您的问题的直接回答（似乎您正在做功课），但我认为它会帮助您入门。为什么不创建一个更符合您的心智模型并从那里建立起来的数据结构呢？

class GraphNode { 

    final String name;
    final List<GraphEdge> adjacentNodes;

    public GraphNode(String name) { 
        this.name = name;
        adjacentNodes = new ArrayList<GraphEdge>();
    }

    public void addAdjacency(GraphNode node, int weight) { 
        adjacentNodes.add(new GraphEdge(node, weight));
    }

}

class GraphEdge {

    final GraphNode node;
    final int weight;

    public GraphEdge(GraphEdge node, int weight) {
        this.node = node;
        this.weight = weight;
    }

}
于 2012-02-26T02:57:13.877 回答
2

假设我的树以邻接表的形式存在

重要的是（为了您的理解）注意您在这种邻接列表中有一个连通图，但我认为这只是一个错字。我将建议将此作为编辑，但我只是希望您注意这一点。从这些行可以看出它是一个图而不是一棵树：

A 2 B 12 I 25
B 3 C 10 H 40 I 8

在这里，您已经在 ABI 有一个圈子：

     A
  12/_\25
   B 8 I

根据定义，有一个圆圈意味着它不可能是一棵树！从我展示这个子图的方式可以看出另外一件事：边有权重，而不是节点。

现在让我们看一下您提供的示例：

A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35

首先，我们可以看到这个邻接列表要么不正确，要么已经针对您的需求进行了优化。这可以（例如）从线条中看出

E 2 F 60 G 38
F 0

这里的第一行显示了从 E 到 F 的边，但第二行说 F 的度数为 0，但度数是由与它相关的边定义的！

如果它是“完整的”，这就是邻接列表的样子：

A 2 B 12 I 25
B 4 A 12 C 10 H 40 I 8
C 3 B 10 D 18 G 55
D 2 C 18 E 44
E 3 D 44 F 60 G 38
F 1 E 60
G 3 C 55 E 38 H 35
H 3 B 40 G 35 I 35

我们可以看到很多冗余，因为每个边都出现两次，这就是为什么您的“优化”邻接列表更适合您的需求 - 是否是这个“完整”示例会做许多无用的检查。但是，只有当您可以确定提供给代码的所有数据都已经“优化”（或者更确切地说是这种格式）时，您才应该依赖它！从现在开始，我将把它当作一个给定的。

让我们谈谈你的数据结构。您当然可以使用您提出的字符串数组，但老实说，我宁愿推荐类似@AmirAfghani 提出的数据结构的东西。使用他的方法会使你的工作更容易（因为它 - 正如他已经指出的那样 - 会更接近你的心理表征），甚至更有效（我猜，不要依赖这个猜测;））因为你会做很多否则对字符串进行操作。在您询问 Prim 算法的标题中，但在您的实际问题中，您说的是Prim 或 Kruskal 的算法。我会选择 Kruskal 只是因为他的算法更简单，而且你似乎都接受了。

克鲁斯卡尔算法

Kruskal 的算法相当简单，基本上是：

  • 从每个节点开始，但没有边

尽可能多地重复以下操作：

  • 从所有未使用/未选择的边缘中选择重量最小的边缘（如果有多个：只需选择其中之一）
  • 检查这个边缘是否会导致一个圆圈，如果是，将其标记为已选择并“丢弃”它。
  • 如果它不会导致圆圈，请使用它并将其标记为已使用/已选择。

就这样。真的就是这么简单。但是我想在这一点上提一件事，我认为它最适合这里：一般没有“最小生成树”，而是“最小生成树”，因为可能有很多，所以你的结果可能会有所不同！

回到你的数据结构！您现在可能明白为什么使用字符串数组作为数据结构是个坏主意。您将在字符串上重复许多操作（例如检查每条边的权重）并且字符串是不可变的，这意味着您不能简单地“丢弃”其中一条边或以任何方式标记其中一条边。使用不同的方法，您可以将权重设置为 -1，甚至删除边缘的条目！

深度优先搜索

从我所见，我认为您的主要问题是确定边缘是否会导致圆圈，对吗？要决定这一点，您可能必须调用深度优先搜索算法并使用它的返回值。基本思想是这样的：从其中一个节点开始（我将此节点称为根节点）并尝试找到通往所选边另一端节点的方法（我将此节点称为目标节点）。（当然在还没有这条边的图中）

  • 选择一个未访问的边缘事件到您的根
  • 将此选择的边缘标记为已访问（或类似的东西，无论你喜欢什么）
  • 对访问边另一侧的节点重复最后两个步骤
  • 每当没有未访问的边缘时，返回一个边缘
  • 如果你回到了你的根，并且没有任何未访问的边缘发生在它上面，那么你就完成了。返回假。
  • 如果你在任何时候访问你的目标节点，你就完成了。返回真。

现在，如果这个方法返回true这个边缘会导致一个圆圈。

于 2012-04-09T06:05:45.630 回答