Graph Swift (BFS, DFS)

Graph 표현

Dictionary + Array

var graph : [String: [String]] = [:]
graph.updateValue(["B","C"], forKey: "A")
graph.updateValue(["A","D"], forKey: "B")
graph.updateValue(["A","G","H","I"], forKey: "C")
graph.updateValue(["D","B","E","F"], forKey: "D")
graph.updateValue(["E","D"], forKey: "E")
graph.updateValue(["F","D"], forKey: "F")
graph.updateValue(["G","C"], forKey: "G")
graph.updateValue(["H","C"], forKey: "H")
graph.updateValue(["I","C","J"], forKey: "I")
graph.updateValue(["J","I"], forKey: "J")

for item in graph {
    print(item)
}

output

(key: "C", value: ["A", "G", "H", "I"])
(key: "I", value: ["I", "C", "J"])
(key: "J", value: ["J", "I"])
(key: "E", value: ["E", "D"])
(key: "H", value: ["H", "C"])
(key: "D", value: ["D", "B", "E", "F"])
(key: "A", value: ["B", "C"])
(key: "F", value: ["F", "D"])
(key: "B", value: ["A", "D"])
(key: "G", value: ["G", "C"])

BFS

• 방문한 노드와 방문할 노드를 담을 Queue 두개를 사용한다.
• 방문할 노드가 없을 때 까지 반복한다.

func bfs(graph : [String:[String]], startNode : String) -> [String] {
    var visitedQueue : [String] = []
    var needVisitQueue : [String] = []
    
    needVisitQueue.append(startNode)
    
    while needVisitQueue.count != 0 {
        let node = needVisitQueue.removeFirst()
        if !visitedQueue.contains(node) {
            visitedQueue.append(node)
            needVisitQueue.append(contentsOf: graph[node]!)
        }
    }
    return visitedQueue
}

["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]

큐동작 과정

[]
["A"]

["A"]
["B", "C"]

["A", "B"]
["C", "A", "D"]

["A", "B", "C"]
["A", "D", "A", "G", "H", "I"]

["A", "B", "C"]
["D", "A", "G", "H", "I"]

["A", "B", "C", "D"]
["A", "G", "H", "I", "D", "B", "E", "F"]

["A", "B", "C", "D"]
["G", "H", "I", "D", "B", "E", "F"]

["A", "B", "C", "D", "G"]
["H", "I", "D", "B", "E", "F", "G", "C"]

["A", "B", "C", "D", "G", "H"]
["I", "D", "B", "E", "F", "G", "C", "H", "C"]

["A", "B", "C", "D", "G", "H", "I"]
["D", "B", "E", "F", "G", "C", "H", "C", "I", "C", "J"]

["A", "B", "C", "D", "G", "H", "I"]
["B", "E", "F", "G", "C", "H", "C", "I", "C", "J"]

["A", "B", "C", "D", "G", "H", "I"]
["E", "F", "G", "C", "H", "C", "I", "C", "J"]

["A", "B", "C", "D", "G", "H", "I", "E"]
["F", "G", "C", "H", "C", "I", "C", "J", "E", "D"]

["A", "B", "C", "D", "G", "H", "I", "E", "F"]
["G", "C", "H", "C", "I", "C", "J", "E", "D", "F", "D"]

["A", "B", "C", "D", "G", "H", "I", "E", "F"]
["C", "H", "C", "I", "C", "J", "E", "D", "F", "D"]

["A", "B", "C", "D", "G", "H", "I", "E", "F"]
["H", "C", "I", "C", "J", "E", "D", "F", "D"]

["A", "B", "C", "D", "G", "H", "I", "E", "F"]
["C", "I", "C", "J", "E", "D", "F", "D"]

["A", "B", "C", "D", "G", "H", "I", "E", "F"]
["I", "C", "J", "E", "D", "F", "D"]

["A", "B", "C", "D", "G", "H", "I", "E", "F"]
["C", "J", "E", "D", "F", "D"]

["A", "B", "C", "D", "G", "H", "I", "E", "F"]
["J", "E", "D", "F", "D"]

["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]
["E", "D", "F", "D", "J", "I"]

["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]
["D", "F", "D", "J", "I"]

["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]
["F", "D", "J", "I"]

["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]
["D", "J", "I"]

["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]
["J", "I"]

["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]
["I"]

시간복잡도

• O(V + E)
• 반복문이 V + E 만큼 수행됨

---

DFS

• 방문할 노드는 Stack 사용
• 방문한 노드엔 Queue 사용

func dfs(graph : [String:[String]], startNode : String) -> [String] {
    var visitedQueue : [String] = []
    var needVisitQueue : [String] = []
    
    needVisitQueue.append(startNode)
    
    while needVisitQueue.count != 0 {
        let node = needVisitQueue.removeLast()
        if !visitedQueue.contains(node) {
            visitedQueue.append(node)
            needVisitQueue.append(contentsOf: graph[node]!)
        }
    }
    return visitedQueue
}

["A", "C", "I", "J", "H", "G", "B", "D", "F", "E"]

시간복잡도

• O(V + E)
• 반복문이 V + E 만큼 수행됨