신장 트리

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다.

신장 트리

• 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 말한다.
  • 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도하다.

최소 신장 트리

• 최소한의 비용으로 구성되는 신장 트리를 찾아야 할 때 어떻게 해야 할까?
• 예를 들어 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우를 생각해보자.
  • 두 도시 A,B를 선택했을 때 A에서 B로 이동하는 경로가 반드시 존재하도록 도로를 설치한다.

 

크루스칼 알고리즘

• 대표적인 최소 신장 트리 알고리즘이다.
• 그리디 알고리즘으로 분류된다.

 

크루스칼 알고리즘의 동작과정

• 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
• 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
  • 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
  • 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
• 모든 간선에 대하여 2번의 과정을 반복한다.

• stpe1 비용이 가장 작은 간선을 선택한다. 따라서 (3,4)가 선택되고 union 연산을 수행한다. 
  • 부모 테이블 union 연산 수행 전 → [1,2,3,4,5,6,7]
  • 부모 테이블 union 연산 수행 후 → [1,2,3,3,5,6,7]

• stpe2 그 다음 비용이 가장 작은 간선인 (4,7)을 선택하고 부모 테이블의 부모노드를 확인한 후 같은 집합이 아니라면 union 연산을 수행한다. 
  • 부모 테이블 union 연산 수행 전 → [1,2,3,3,5,6,7]
  • 부모 테이블 union 연산 수행 후 → [1,2,3,3,5,6,3]

• stpe3 그 다음 비용이 가장 작은 간선인 (4,6)을 선택하고 부모 테이블의 부모노드를 확인한 후 같은 집합이 아니라면 union 연산을 수행한다. 
  • 부모 테이블 union 연산 수행 전 → [1,2,3,3,5,6,3]
  • 부모 테이블 union 연산 수행 후 → [1,2,3,3,5,3,3]

• stpe4 그 다음 비용이 가장 작은 간선인 (6,7)을 선택하고 부모 테이블의 부모노드를 확인한 후 같은 집합이 아니라면 union 연산을 수행한다.
  • 부모 테이블 union 연산 수행 전 → [1,2,3,3,5,3,3]
  • 부모 테이블 union 연산 수행 후 → [1,2,3,3,5,3,3]
  • 노드 6의 부모노드는 3이고 노드 7의 부모노드도 3이기 때문에 사이클이 발생하므로 신장 트리에서 제외한다.

• stpe5 그 다음 비용이 가장 작은 간선인 (1,2)을 선택하고 부모 테이블의 부모노드를 확인한 후 같은 집합이 아니라면 union 연산을 수행한다.
  • 부모 테이블 union 연산 수행 전 → [1,2,3,3,5,3,3]
  • 부모 테이블 union 연산 수행 후 → [1,1,3,3,5,3,3]

• stpe6 그 다음 비용이 가장 작은 간선인 (2,6)을 선택하고 부모 테이블의 부모노드를 확인한 후 같은 집합이 아니라면 union 연산을 수행한다.
  • 부모 테이블 union 연산 수행 전 → [1,1,3,3,5,3,3]
  • 부모 테이블 union 연산 수행 후 → [1,1,1,3,5,3,3]
  • 노드 2의 부모노드는 1이고 노드 6의 부모노드는 3이다.
  • find 연산을 통해서 노드 1의 부모노드와 노드 3의 부모노드를 비교해 union연산을 수행하면 노드 3의 부모노드 테이블이 갱신된다.

• stpe7 그 다음 비용이 가장 작은 간선인 (2,3)을 선택하고 부모 테이블의 부모노드를 확인한 후 같은 집합이 아니라면 union 연산을 수행한다.
  • 부모 테이블 union 연산 수행 전 → [1,1,1,3,5,3,3]
  • 부모 테이블 union 연산 수행 후 → [1,1,1,3,5,3,3]
  • 노드 2의 부모노드는 1이고 노드 3의 부모노드도 1이기 때문에 사이클이 발생하므로 신장 트리에서 제외한다.

 

• stpe8 그 다음 비용이 가장 작은 간선인 (5,6)을 선택하고 부모 테이블의 부모노드를 확인한 후 같은 집합이 아니라면 union 연산을 수행한다.
  • 부모 테이블 union 연산 수행 전 → [1,1,1,3,5,3,3]
  • 부모 테이블 union 연산 수행 후 → [1,1,1,3,1,1,3]
  • 노드 5의 부모노드는 5이고 노드 6의 부모노드는 3이다.
  • find 연산을 통해서 노드 6의 부모노드는 3이고 3의 부모노드는 1이기 때문에 1의 부모노드와 5의 부모노드를 비교해 union 연산을 수행하면 노드5의 부모노드는 1로 갱신된다.
  • 그리고 find 연산을 통해서 노드 6의 부모노드도 1로 갱신된다.

 

• stpe9 그 다음 비용이 가장 작은 간선인 (1,5)를 선택하고 부모 테이블의 부모노드를 확인한 후 같은 집합이 아니라면 union 연산을 수행한다.
  • 부모 테이블 union 연산 수행 전 → [1,1,1,3,1,1,3]
  • 부모 테이블 union 연산 수행 후 → [1,1,1,3,1,1,3]
  • 노드 1의 부모노드는 1이고 노드 5의 부모노드도 1이기 때문에 사이클이 발생하므로 신장 트리에서 제외한다.

 

 

크루스칼 알고리즘 소스코드

// 노드의 개수, 합집합 연산 개수 입력받기
let input = readLine()!.components(separatedBy: " ").map({Int($0)!})
// 노드의 개수
let n = input[0]
// 합집합 연산 개수
let union = input[1]

// 부모노드배열 초기화
var parentArr = Array(repeating: 0, count: n + 1)

// 부모노드를 자기자신으로 초기화
for i in 0...n {
    parentArr[i] = i
}

// 부모노드 찾기
func findParent(node: Int) -> Int {
    // 현재노드의 부모노드가 루트노드가 아니면
    if parentArr[node] != node {
        // 루트노드를 찾을 때까지 재귀적으로 호출하면서 결과값은 부모노드 테이블에 저장
        parentArr[node] = findParent(node: parentArr[node])
    }
    // 현재 노드가 자기자신이라면 현재 부모노드 테이블 반환
    return parentArr[node]
}

// 합집합 연산 수행
func unionParent(a: Int, b: Int) {
    // A노드의 부모노드 찾기
    let a = findParent(node: a)
    // B노드의 부모노드 찾기
    let b = findParent(node: b)
     
    // a의 부모노드가 b의 부모노드보다 작다면
    if a < b {
        // b의 노드에 a의 부모노드 저장
        parentArr[b] = a
    } else {
        // a의 노드에 b의 부모노드 저장
        parentArr[a] = b
    }
}

var edges = [(Int,Int,Int)]()
var result = 0

// 모든 간선 정보 입력받기
for _ in 0..<union {
    let inputUnion = readLine()!.components(separatedBy: " ").map({Int($0)!})
   
    let cost = inputUnion[2] //
    let a = inputUnion[0]
    let b = inputUnion[1]
    
    edges.append((cost,a,b))
}

// 비용순으로 오름차순 정렬
edges.sort(by: {$0.0 < $1.0})

// 간선 정보를 하나씩 확인
for edge in edges {
    let cost = edge.0
    let a = edge.1
    let b = edge.2
    
    // 사이클이 발생하지 않는 경우에만 집합에 포함
    if findParent(node: a) != findParent(node: b) {
        unionParent(a: a, b: b)
        result += cost
    }
}

print(result)

 

크루스칼 알고리즘의 시간 복잡도

• 간선의 개수가 E개 일때 O(ElogE)의 시간 복잡도를 가진다.

 

위상 정렬

• 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할때 사용할 수 있는 알고리즘이다.
• 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 알고리즘이다.
  • 진입 차수
    • 특정한 노드로 들어오는 간선의 개수
  • 진출 차수
    • 특정한 노드에서 나가는 간선의 개수

위상정렬의 특징

• DAG에 대해서만 수행할 수 있다.
  • DAG → 순환하지 않는 방향 그래프(사이클이 없는 그래프)
• 여러가지 답이 존재할 수 있다.
  • 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면 여러가지 답이 존재한다.
• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다.
  • 사이클에 포함된 원소 중에서 어떠한 원소도 큐에 들어가지 못한다.
• 스택을 활용한 DFS를 이용해 위상 정렬을 수행할 수도 있다.

 

위상정렬 알고리즘 동작과정

• 진입차수가 0인 모든 노드를 큐에 넣는다.
• 큐가 빌 때까지 다음의 과정을 반복한다.
  • 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
  • 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
• 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다.

• step1 큐에 들어있는 노드1을 꺼낸다. 
• 노드 1과 연결되어 있는 간선들을 제거하면 노드 2와 노드 5의 진입차수가 0이 되므로 노드 2와 노드5를 큐에 넣는다.

• step2 그 다음 큐에 들어있는 노드 2를 꺼낸다.
• 노드 2와 연결되어 있는 간선들을 제거하면 노드 3의 진입차수가 0이 되므로 노드 3을 큐에 넣는다.

• step3 그 다음 큐에 들어있는 노드 5를 꺼낸다.
• 노드 5와 연결되어 있는 간선들을 제거하면 노드 6의 진입차수가 0이 되므로 노드 6을 큐에 넣는다.

• step4 그 다음 큐에 들어있는 노드 3을 꺼낸다.
• 노드 3과 연결되어 있는 간선들을 제거하면 새롭게 진입차수가 0이 되는 노드가 없으므로 다음 단계로 넘어간다.

• step5  그 다음 큐에 들어있는 노드 6을 꺼낸다.
• 노드 6과 연결되어 있는 간선들을 제거하면 노드 4의 진입차수가 0이 되므로 노드 4를 큐에 삽입한다.

• step6  그 다음 큐에 들어있는 노드 4를 꺼낸다.
• 노드 4와 연결되어 있는 간선들을 제거하면 노드 7의 진입차수가 0이 되므로 노드 7을 큐에 삽입한다.

• step7 그 다음 큐에 들어있는 노드 7을 꺼낸다.
• 노드 7과 연결되어 있는 간선들을 제거하면 새롭게 진입차수가 0이 되는 노드가 없으므로 다음 단계로 넘어간다.

 

위상 정렬 알고리즘 소스

class Heap<T: Comparable> {
    var heapArray: [T]
    var count: Int {
        return heapArray.count
    }
    var isEmpty: Bool {
        return heapArray.isEmpty
    }
    init(_ n: [T]) {
        heapArray = n
    }
    func popRoot() -> T?{
        if !heapArray.isEmpty {
            let temp = heapArray[heapArray.count - 1]
            heapArray[heapArray.count - 1] = heapArray[0]
            heapArray[0] = temp
        }
        let rootValue = heapArray.popLast()
        
        return rootValue
        
    }
    func push(_ n: T) {
        heapArray.append(n)
    }
}

// -----------------------------------------------------------------

// 노드 개수와 간선 개수 입력받기
let input = readLine()!.components(separatedBy: " ").map({Int($0)!})
// 모든 노드에 대한 진입차수 0으로 초기화
var indegree = Array(repeating: 0, count: input[0]+1)
// 각 노드에 연결된 간선 정보 입력받을 배열 초기화
var graph = Array(repeating: [Int](), count: input[0]+1)

// 간선 정보 입력받기
for _ in 0..<input[1] {
    let input = readLine()!.components(separatedBy: " ").map({Int($0)!})
    let inNode = input[0]
    let outNode = input[1]
    
    // 각각의 노드에 이동할 노드번호 담기
    graph[inNode].append(outNode)
    
    // 이동할 노드에 진입차수 1씩 증가시키기
    indegree[outNode] += 1
}

func topologySort() {
    // 위상 정렬 결과 담을 배열 초기화
    var result = [Int]()
    
    let q = Heap([Int]())
    //var q = Heap([Int](), isMaxHeap: true)
    
    // 첫 시작시 진입차수가 0인 노드 큐에 삽입
    for i in 1..<input[0]+1 {
        if indegree[i] == 0 {
            q.push(i)
        }
    }
    
    // 큐가 빌때까지 반복
    while !q.isEmpty {
        let now = q.popRoot()!
        result.append(now)
        
        // 현재 노드와 연결되어 있는 노드들의 진입차수 1씩 빼주기
        for i in graph[now] {
            indegree[i] -= 1
            
            // 새롭게 진입차수가 0인 노드 큐에 넣기
            if indegree[i] == 0 {
                q.push(i)
            }
        }
    }
    // 위상 정렬 결과 출력
    print(result)
}

topologySort()

 

위상 정렬의 시간 복잡도

• 노드와 간선을 모두 확인하므로 O(V+E)가 된다.