[Swift] The Swift Arcade Data Structures and AlgorithmsBootcamp - Graphs

그래프는 꼭지점(Vertices)과 변(Edges) 로 이루어져 있을 뿐 !

변 == 꼭지점과 꼭지점을 잇는 선

 

꼭지점을 노드라고 표현하겠습니당

 

그래프 데이터를 표현하는 기본 데이터 구조

[1]  Edges Lists

노드와 꼭지점을 잇는 변을 List로 나타낸다

ex) 0 -> 1 은 [0,1]로 표현한다

 

장점 : 간단하다

단점 : List에서 특정 변(Edge)을 찾아야하는 경우 모든 목록을 검색하는 선형 검색이 필요하다 O(n)

 

[2] Adjacency Matrices

노드로 이루어진 2차원 배열에서 연결된 꼭지점을 1로 표현하여 변을 나타낸다

 

장점 : 조회가 매우 빠르다 O(1)

단점 : 공간이 효율적이지 않다. 만약 연결된 곳이 많지 않다면 거의 대부분 0이 차지할 것이다

 

 

[3]  Adjacency Lists

각 노드 마다의 이웃을 목록으로 기록하는 List / 1,2 의 장점을 결합했다

 

 

---

데이터 구조를 사용하여 그래프를 검색할 수 있는 일반적인 두가지 방법

 

BFS, DFS 모두 방문한 노드를 기록하는 것이 필요하다 그렇지 않으면 무한 굴레에서 벗어나지 못할수도 ..!

 

1. Breadth First Search

점진적으로 탐색 범위를 넓혀가는 방법

 

Queue를 사용한다

---

1-2. 첫 노드를 Queue에 넣는다

1-2. Queue에서 노드를 꺼낸다

 

2-1. 꺼내진 노드의 방문하지 않은 이웃한 노드들을 모두 Queue에 넣는다 / 없을 경우 2-2로

2-2. Queue에서 노드를 꺼낸다

 

Queue가 빌 때까지 2를 계속 반복한다

---

 

코드로 보자

(adj는 그래프를 Adjacency Lists로 표현한 배열, queue는 구현되어있다고 치자)

 

func BFS(s: Int) -> [Int] {
        
        var result = [Int]()
        var visited = adj.map { _ in false }
        var queue = Queue<Int>()
        
        visited[s] = true
        queue.add(s)
        result.append(s)
        
        while queue.count > 0 {
            let current = queue.remove()!
            
            for n in adj[current] {
                if visited[n] == false {
                    visited[n] = true
                    queue.add(n)
                    result.append(n)
                }
            }
         }
        
        return result
    }

탐색할 노드를 Queue에 넣고 바로 결과에도 추가해준다. FIFO 인 Queue이기 때문

 

 

2. Depth First Search

경로 하나씩 끝까지 파는 방법

 

Stack을 사용한다

---

1-2. 첫 노드를 Stack에 넣는다

1-2. Stack에서 노드를 pop

 

2-1. 꺼내진 노드의 방문하지 않은 이웃한 노드들을 모두 Stack에 넣는다 / 없을 경우 2-2로

2-2. Stack에서 노드를 pop

 

Stack이 빌 때까지 2를 계속 반복한다

---

코드로 보자

(stack은 구현되어 있다고 치자)

func DFS(s: Int) -> [Int] {
        
        var result = [Int]()
        var visited = adj.map { _ in false }
        var stack = Stack<Int>()
        
        visited[s] = true
        stack.push(s)
        
        while stack.count > 0 {
            let current = stack.pop()!
            result.append(current)
            
            for n in adj[current] {
                if visited[n] == false {
                    visited[n] = true
                    stack.push(n)
                }
            }
        }
        
        return result
    }
}

탐색할 노드를 Stack에 넣을 때 result에 추가해주지 않고, pop 할 때 추가해준다. FILO인 Stack 때문

 

BFS? DFS?

BFS	DFS
Better near the top - Social networks (FB, LinkedIn) - Nearby peers in games	Better faraway - Game Simulations