This article is a translation of Swift Algorithm Club. Swift Algorithm Club is an open source project produced by Raywenderlich.com to realize algorithms and data structures by Swift. Currently, there are 18000+⭐️ on GitHub. I have made a brief statistics, and there are about 100 algorithms and data structures. It’s basically a good resource for iOSer learning algorithms and data structures. 🐙andyRon/ swift-algorithm-club-CN is my project of learning and translating for Swift Algorithm Club. Due to the limited capacity, if you find any errors or improper translation, please correct them. Welcome to Pull Request. Also welcome interested, have time partners to participate in translation and learning 🤓. Of course, we welcome ⭐️, 🤩🤩 ️ ⭐ ⭐. A translation of this article and the code can be found at 🐙swift-algorithm-club-cn/Minimum Spanning Tree(Unweighted)

Minimum Spanning Tree (Unweighted Graph)

A minimum spanning tree describes a path that contains the minimum number of edges needed to access each node in the graph.

See below:

If we start at node A and want to access every other node, what is the most efficient path? We can calculate it using a minimum spanning tree algorithm.

This is the minimum spanning tree of the graph. It is indicated by bold edges:

Drawn as a more general tree, it looks like this:

To calculate the minimum spanning tree on an unweighted graph, we can use a breadth-first search algorithm. Breadth-first search starts at the source node and first traverses the graph by exploring the immediate neighbor nodes before moving to the next-level neighbor. If we adjust this algorithm by selectively removing edges, it can turn the graph into a minimum spanning tree.

Let’s work through this example step by step. We start with the source node A, add it to the queue and mark it as visited.

queue.enqueue(a)
a.visited = true
Copy the code

The queue is now [a]. As with breadth-first search, we de-queue node A at the front of the queue and enqueue its immediate neighbors, nodes B and H. Mark them as visited.

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

The queue is now [b, h]. Remove NODE B from the queue and add node C to the queue. Mark it as accessed. Remove edges from B to H because H has already been accessed.

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

The queue is now [H, C]. Dequeue H and enqueue neighbor nodes G and I, and mark them as visited.

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

The queue is now [C, G, I]. Dequeue C and enqueue neighbor nodes D and f, and mark them as visited. Delete the edge between c and I because I is already accessed.

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

The queue is now [G, I, D, f]. G out of the team. All its neighbors had already been discovered, so there was nothing to join the team. Delete the edge from g to F, and the edge from g to I, because f and I are already found.

queue.dequeue()   // g
g.removeEdgeTo(f)
g.removeEdgeTo(i)
Copy the code

The queue is now [I, D, f]. I out of the team. There is no other way for this node.

queue.dequeue()   // i
Copy the code

The queue is now [d, f]. Remove D from the team and add neighbor e to the team. Mark it as accessed. Delete edges from d to f because F is already accessed.

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

The queue is now [f, e]. Dequeue f. Delete the edge between f and e because e has already been accessed.

queue.dequeue()   // f
f.removeEdgeTo(e)
Copy the code

The queue is now [e]. E out of the team.

queue.dequeue()   // e
Copy the code

The queue is empty, which means that the minimum spanning tree has been calculated.

The code is as follows:

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
}
Copy the code

This function returns a new Graph object that describes only the minimum spanning tree. In the graph, this would be the graph with only bold edges.

Put this code on the playground to test:

let graph = Graph(a)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"]]
Copy the code

Note: On an unweighted graph, any spanning tree is always a minimum spanning tree. This means that you can also use depth-first search to find minimum spanning trees.

Translated by Andy Ron and proofread by Andy Ron