Chapter 37: Graphs Challenges

Challenge 1: Count the number of paths

유향 그래프(directed graph)에서 두 정점(vertices) 사이의 경로(paths) 수를 계산하는 메서드(method)를 작성한다. 아래 예제 그래프(graph)는 A에서 E까지 5개의 경로(paths)가 있다.

 

Solution

목표는 그래프(Graph)에서 두 정점(vertices) 사이의 경로(paths) 수를 찾는 함수(function)를 작성하는 것이다. 한 가지 해결책은 깊이 우선 순회(depth-first traversal)를 수행하고, 방문한 정점(vertices)을 추적(track)하는 것이다.

extension Graph where Element: Hashable {
    public func numberOfPaths(from source: Vertex<Element>, to destination: Vertex<Element>) -> Int {
        var numberOfPaths = 0 //출발지와 목적지 사이에서 발견한 경로의 수를 추적한다.
        var visited: Set<Vertex<Element>> = [] //방문한 모든 정점을 추적한다.
        paths(from: source, to: destination, visited: &visited, pathCount: &numberOfPaths)
        //helper 메서드를 재귀적으로 호출한다.
        
        return numberOfPaths
    }
}

numberOfPaths 함수(function) 바로 뒤에 다음을 추가한다.

extension Graph where Element: Hashable {
    func paths(from source: Vertex<Element>, to destination: Vertex<Element>, visited: inout Set<Vertex<Element>>, pathCount: inout Int) {
        visited.insert(source) //방문한 정점에 source(from)를 추가하면서 알고리즘을 시작한다.
        if source == destination { //source와 destination가 같은지 확인한다.
            pathCount += 1 //같다면, 경로가 존재하는 것이므로 pathCount를 1 추가한다.
        } else { //source와 destination가 같지 않은 경우
            let neighbors = edges(from: source) //source에서 모든 인접 간선을 가져온다.
            for edge in neighbors {
                //해당 source의 모든 간선에서 이전에 방문하지 않은 인접 정점을 재귀적으로 탐색하여 destination 정점에 대한 경로를 찾는다.
                if !visited.contains(edge.destination) {
                    paths(from: edge.destination, to: destination, visited: &visited, pathCount: &pathCount)
                }
            }
        }
        visited.remove(source)
        //방문한 정점 set에서 source를 제거하여, 해당 node에 대한 다른 경로를 계속해서 찾을 수 있도록 한다.
    }
}

깊이 우선 그래프 탐색(depth-first graph traversal)을 구현하고 있다. 목적지(destination)에 도달할 때까지 경로(path)를 재귀적으로(recursively) 진행(dive down)하고, 스택(stack)에서 pop하면서 추적(back-track)한다. 시간 복잡도(time complexity)는 O(V+E)이다.

let graph = AdjacencyList<String>()

let a = graph.createVertex(data: "A")
let b = graph.createVertex(data: "B")
let c = graph.createVertex(data: "C")
let d = graph.createVertex(data: "D")
let e = graph.createVertex(data: "E")

graph.add(.directed, from: a, to: b, weight: 0)
graph.add(.directed, from: a, to: d, weight: 0)
graph.add(.directed, from: a, to: e, weight: 0)
graph.add(.directed, from: a, to: c, weight: 0)
graph.add(.directed, from: b, to: d, weight: 0)
graph.add(.directed, from: b, to: c, weight: 0)
graph.add(.directed, from: d, to: e, weight: 0)
graph.add(.directed, from: c, to: e, weight: 0)

print(graph)
// 0: A ---> [ 1: B, 3: D, 4: E, 2: C ]
// 1: B ---> [ 3: D, 2: C ]
// 2: C ---> [ 4: E ]
// 3: D ---> [ 4: E ]
// 4: E ---> [  ]
print("Number of paths: \(graph.numberOfPaths(from: a, to: e))") // 5

---

Challenge 2: Graph your friends

Vincent는 Chesley, Ruiz, Patrick 세 명의 친구가 있다. Ruiz는 Ray, Sun, Vincent의 친구이다. Patrick은 Cole, Kerry의 친구이다. Cole은 Ruiz, Vincent의 친구이다. 이 친구 관계 그래프(graph)를 나타내는 인접 리스트(adjacency list)를 작성한다. Ruiz와 Vincent 둘 모두의 친구는 누구인가?

 

Solution

인접 리스트(AdjacencyList) API를 사용해 구현한다. 0이 아닌 어떤 값이든 가중치(weight)로 사용해도 좋지만, 가장 좋은 기본값은 1이다.

let graph = AdjacencyList<String>()

let vincent = graph.createVertex(data: "vincent")
let chesley = graph.createVertex(data: "chesley")
let ruiz = graph.createVertex(data: "ruiz")
let patrick = graph.createVertex(data: "patrick")
let ray = graph.createVertex(data: "ray")
let sun = graph.createVertex(data: "sun")
let cole = graph.createVertex(data: "cole")
let kerry = graph.createVertex(data: "kerry")

graph.add(.undirected, from: vincent, to: chesley, weight: 1)
graph.add(.undirected, from: vincent, to: ruiz, weight: 1)
graph.add(.undirected, from: vincent, to: patrick, weight: 1)
graph.add(.undirected, from: ruiz, to: ray, weight: 1)
graph.add(.undirected, from: ruiz, to: sun, weight: 1)
graph.add(.undirected, from: patrick, to: cole, weight: 1)
graph.add(.undirected, from: patrick, to: kerry, weight: 1)
graph.add(.undirected, from: cole, to: ruiz, weight: 1)
graph.add(.undirected, from: cole, to: vincent, weight: 1)
print(graph)
// 0: vincent ---> [ 1: chesley, 2: ruiz, 3: patrick, 6: cole ]
// 1: chesley ---> [ 0: vincent ]
// 2: ruiz ---> [ 0: vincent, 4: ray, 5: sun, 6: cole ]
// 3: patrick ---> [ 0: vincent, 6: cole, 7: kerry ]
// 4: ray ---> [ 2: ruiz ]
// 5: sun ---> [ 2: ruiz ]
// 6: cole ---> [ 3: patrick, 2: ruiz, 0: vincent ]
// 7: kerry ---> [ 3: patrick ]

단순히 그래프(graph)를 확인해 서로 친구인지 확인할 수도 있다.

print("Ruiz and Vincent both share a friend name Cole")

프로그램으로 이 문제를 해결하려면 요소(element)가 Hashable이라는 것을 사용해, Ruiz와 Vincent 친구들간의 교집합(intersection)을 찾아 해결할 수 있다.

let vincentsFriends = Set(graph.edges(from: vincent).map { $0.destination.data })
let mutual = vincentsFriends.intersection(graph.edges(from: ruiz).map { $0.destination.data })
print(mutual) // ["cole"]