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

Swift算法俱乐部

最小生成树（未加权图）（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"]]