그래프, BSF 구현[Swift]

그래프 구현

문제를 풀다보면 그래프를 구현하여 DFS, BFS 알고리즘을 구현해야 할 때가 많다

 

간선배열, 노드의 개수로 그래프를 구현(인접 리스트, 무 방향성)

간선배열(wires)= [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]

노드의 수(n) = 9

위와같은 모습의 그래프를 인접리스트로 구현하면 오른쪽 표처럼 구현할 수 있다.

표의 칠해진 부분은 노드의 번호, 칠해지지 않은 부분은 해당 노드와 연결된 노드다.

해당 리스트를 Swift 언어로 표현

var graph: [Int: [Int]] = [:]

딕셔너리 형태로 키, 벨류(배열)로 저장하면 된다.

그래프를 초기화

let wires= [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] //간선의 배열
let n = 9 //노드의 수

var graph: [Int: [Int]] = [:]

//그래프의 키를 우선 설정한다. 노드는 1번부터 9번까지 있으므로 1에서 9까지의 노드를 추가한다
//초기엔 value는 []로 한다. graph를 생성할 때 value 값은 [Int]로 설정했기 때문
for i in 1...n{
    graph.updateValue([], forKey: i)
    }

이제 노드에 연결된 노드들을 추가해준다.

let wires= [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] //간선의 배열
let n = 9 //노드의 수

var graph: [Int: [Int]] = [:]

for i in 1...n{
    graph.updateValue([], forKey: i)
    }

//wires의 요소 1개씩 접근해가며
//wires[0], [1]은 각각 노드의 번호고 1번은 0번과 연결되고 0번은 1번과 연결되었다는 뜻이다.
//
for wire in wires{
    graph[wire[0]]?.append(wire[1])
    graph[wire[1]]?.append(wire[0])
}

---

BFS 구현(인접리스트활용)

 func bfs(_ start: Int){
        var visited = [Bool](repeating: false, count: n + 1)
        var queue = [Int]()
        
        queue.append(start)
        visited[start] = true
        
        while !queue.isEmpty{
            let now = queue.removeFirst()
            print(now)
            
            for i in graph[now]!{
                if !visited[i]{
                    queue.append(i)
                    visited[i] = true
                }
            }
        }
    }

 

 

 

*추가

키를 기준으로 Dictionary를 정렬하는 방법

var sortedgraph = graph.sorted(){ (first, second) in
        return first.key < second.key
    }