使用Prims算法从邻接列表中查找最小生成树,其中邻接列表在字符串数组中

Question

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

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.所以我原计划将这整个事物表示为一个名为String的数组Graph[8].每一行都是数组中的不同插槽.我无法通过Prims或Kruskalls算法找出如何实现这一目标.

Answer 1

这不是你的问题的直接答案(似乎你正在做功课),但我认为这将有助于你开始.为什么不创建一个更接近您的心智模型并从那里积累的数据结构？

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;
    }

}

Answer 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 的算法相当简单，基本上是：

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

尽可能频繁地重复以下操作：

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

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

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

深度优先搜索

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

• 选择与您的根相关的一个未访问的边
• 将所选边缘标记为已访问（或类似的内容，无论您喜欢什么）
• 对访问边另一侧的节点重复最后两个步骤
• 每当没有未访问过的边时，返回一条边
• 如果您回到了根并且没有未访问过的边缘，那么您就完成了。返回假。
• 如果您在任何时候访问您的目标节点，您就完成了。返回真。

现在，如果此方法返回true此边缘将导致一个圆。