【译】Swift算法俱乐部-最小生成树（未加权图）

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Minimum Spanning Tree(Unweighted))

---

最小生成树（未加权图）（Minimum Spanning Tree (Unweighted Graph)）

最小生成树描述了包含访问图中每个节点所需的最小数目边的路径。

看下图：

如果我们从节点a开始并想要访问每个其他节点，那么最有效的路径是什么？ 我们可以使用最小生成树算法来计算它。

这是图的最小生成树。 它由粗体边表示：

绘制为更一般形式的树，它看起来像这样：

要计算未加权图上的最小生成树，我们可以使用广度优先搜索 算法。广度优先搜索从源节点开始，并在移动到下一级邻居之前首先通过探索直接邻居节点来遍历图。如果我们通过选择性地删除边来调整此算法，那么它可以将图转换为最小生成树。

让我们逐步完成这个例子。 我们从源节点a开始，将其添加到队列中并将其标记为已访问。

queue.enqueue(a)
a.visited = true

队列现在是[a]。 与广度优先搜索一样，我们将队列前面的节点a出队，并将其直接邻居节点b和h入队。 将它们标记为访问过。

queue.dequeue()   // a
queue.enqueue(b)
b.visited = true
queue.enqueue(h)
h.visited = true

队列现在是[b, h]。 将b出队并将邻居节点c入队。 将其标记为已访问。 将b到h边移除，因为已经访问过h。

queue.dequeue()   // b
queue.enqueue(c)
c.visited = true
b.removeEdgeTo(h)

队列现在是[h, c]。 将h出队并将邻居节点g和i入队，并将它们标记为已访问。

queue.dequeue()   // h
queue.enqueue(g)
g.visited = true
queue.enqueue(i)
i.visited = true

队列现在是[c, g, i]。 将c出队并将邻居节点d和f入队，并将它们标记为已访问。 删除c和i之间的边，因为已经访问了i。

queue.dequeue()   // c
queue.enqueue(d)
d.visited = true
queue.enqueue(f)
f.visited = true
c.removeEdgeTo(i)

队列现在是[g, i, d, f]。 出队g。 它的所有邻居都已经被发现了，所以没有什么可以入队的。 删除g到f的边，以及g到i的边，因为已经发现了f和i。

queue.dequeue()   // g
g.removeEdgeTo(f)
g.removeEdgeTo(i)

队列现在是[i, d, f]。 出队i。 这个节点没有别的办法。

queue.dequeue()   // i

队列现在是[d, f]。 将d出队并将邻居节点e入队。 将其标记为已访问。 删除d到f的边，因为已经访问了f。

queue.dequeue()   // d
queue.enqueue(e)
e.visited = true
d.removeEdgeTo(f)

队列现在是[f, e]。 出列f。 删除f和e之间的边，因为已经访问过e。

queue.dequeue()   // f
f.removeEdgeTo(e)

队列现在是[e]。 出队e。

queue.dequeue()   // e

队列为空，这意味着已计算出最小生成树。

代码如下：

func breadthFirstSearchMinimumSpanningTree(graph: Graph, source: Node) -> Graph {
  let minimumSpanningTree = graph.duplicate()

  var queue = Queue<Node>()
  let sourceInMinimumSpanningTree = minimumSpanningTree.findNodeWithLabel(source.label)
  queue.enqueue(sourceInMinimumSpanningTree)
  sourceInMinimumSpanningTree.visited = true

  while let current = queue.dequeue() {
    for edge in current.neighbors {
      let neighborNode = edge.neighbor
      if !neighborNode.visited {
        neighborNode.visited = true
        queue.enqueue(neighborNode)
      } else {
        current.remove(edge)
      }
    }
  }

  return minimumSpanningTree
}

此函数返回一个新的Graph对象，该对象仅描述最小生成树。 在图中，这将是仅包含粗体边的图。

将此代码放在playground上，进行测试：

let graph = Graph()

let nodeA = graph.addNode("a")
let nodeB = graph.addNode("b")
let nodeC = graph.addNode("c")
let nodeD = graph.addNode("d")
let nodeE = graph.addNode("e")
let nodeF = graph.addNode("f")
let nodeG = graph.addNode("g")
let nodeH = graph.addNode("h")
let nodeI = graph.addNode("i")

graph.addEdge(nodeA, neighbor: nodeB)
graph.addEdge(nodeA, neighbor: nodeH)
graph.addEdge(nodeB, neighbor: nodeA)
graph.addEdge(nodeB, neighbor: nodeC)
graph.addEdge(nodeB, neighbor: nodeH)
graph.addEdge(nodeC, neighbor: nodeB)
graph.addEdge(nodeC, neighbor: nodeD)
graph.addEdge(nodeC, neighbor: nodeF)
graph.addEdge(nodeC, neighbor: nodeI)
graph.addEdge(nodeD, neighbor: nodeC)
graph.addEdge(nodeD, neighbor: nodeE)
graph.addEdge(nodeD, neighbor: nodeF)
graph.addEdge(nodeE, neighbor: nodeD)
graph.addEdge(nodeE, neighbor: nodeF)
graph.addEdge(nodeF, neighbor: nodeC)
graph.addEdge(nodeF, neighbor: nodeD)
graph.addEdge(nodeF, neighbor: nodeE)
graph.addEdge(nodeF, neighbor: nodeG)
graph.addEdge(nodeG, neighbor: nodeF)
graph.addEdge(nodeG, neighbor: nodeH)
graph.addEdge(nodeG, neighbor: nodeI)
graph.addEdge(nodeH, neighbor: nodeA)
graph.addEdge(nodeH, neighbor: nodeB)
graph.addEdge(nodeH, neighbor: nodeG)
graph.addEdge(nodeH, neighbor: nodeI)
graph.addEdge(nodeI, neighbor: nodeC)
graph.addEdge(nodeI, neighbor: nodeG)
graph.addEdge(nodeI, neighbor: nodeH)

let minimumSpanningTree = breadthFirstSearchMinimumSpanningTree(graph, source: nodeA)

print(minimumSpanningTree) // [node: a edges: ["b", "h"]]
                           // [node: b edges: ["c"]]
                           // [node: c edges: ["d", "f"]]
                           // [node: d edges: ["e"]]
                           // [node: h edges: ["g", "i"]]

注意： 在未加权的图上，任何生成树始终是最小生成树。 这意味着您还可以使用深度优先搜索来查找最小生成树。

作者：Chris Pilcher， Matthijs Hollemans
翻译：Andy Ron
校对：Andy Ron