최소 신장 트리 (가중치 없는 그래프)

최소 신장 트리는 그래프의 모든 노드를 방문하는 데 필요한 가장 적은 수의 간선으로 구성된 경로를 의미한다.

다음 그래프를 살펴보자:

Graph

노드 a에서 시작해 모든 노드를 방문하려면 가장 효율적인 경로는 무엇일까? 최소 신장 트리 알고리즘을 사용해 이를 계산할 수 있다.

다음은 이 그래프의 최소 신장 트리다. 굵은 선으로 표시된 간선이 최소 신장 트리를 나타낸다:

Minimum spanning tree

이를 일반적인 트리 형태로 그리면 다음과 같다:

An actual tree

가중치 없는 그래프에서 최소 신장 트리를 계산하려면 너비 우선 탐색 알고리즘을 사용할 수 있다. 너비 우선 탐색은 시작 노드에서 출발해 바로 이웃한 노드를 먼저 탐색한 후, 다음 레벨의 노드를 탐색한다. 이 알고리즘을 약간 수정해 특정 간선을 제거하면 그래프를 최소 신장 트리로 변환할 수 있다.

예제를 따라가 보자. 시작 노드 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의 모든 이웃 노드가 이미 방문되었으므로 큐에 추가할 노드가 없다. g에서 f와 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 객체를 반환한다. 위 그림에서 굵은 선으로 표시된 그래프가 이에 해당한다.

이 코드를 플레이그라운드에 넣고 다음과 같이 테스트할 수 있다:

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