[MIT 6.006 정리] Lec 13. 그래프 (그래프 탐색, 너비 우선 탐색 (BFS))

* 본 포스팅은 기본적으로 edwith 플랫폼을 통해 제공되고 있는 MIT 6.006 Introduction to Algorithms (Fall 2011) 강의 내용을 바탕으로 정리한 것입니당 :D

 

------- * ------- * ------- * -------

 

* 그래프 탐색 (Graph search)

• 그래프 G = (V, E)
  • V = 정점(vertices, == 노드 nodes) 의 집합,  E = 간선(edges) 의 집합
  • e = {v, w} (un-ordered pairs of vetices) 또는 (v, w) (ordered pairs) ∈ E
• 그래프 탐색 (graph search) 은 이러한 그래프 구조를 탐험(explore) 하는 것!
• 응용 예시
  • 웹 크롤링 (동적으로 새로운 페이지가 생성되고 있는 웹 공간에서 길을 잃지 않기 위해서...!)
  • 소셜 네트워킹 서비스 (친구 추천 등)
  • 네트워크 브로드캐스트 (인터넷, 인트라넷 등에서 메시지를 전달/ 패킷을 전송하고자 할 때!)
  • 가비지 컬렉션 (프로그램에서 더이상 도달할 수 없게 된 데이터들을 제거하여 활용 가능한 메모리를 새로 확보하는 것)
  • 모델 체킹 (유한한(finite) 모델 (코드의 일부분이나 회로, 칩 등) 이 존재할 때, 실제로 생각한 대로 작동하는지 증명하기 위해 회로/프로그램이 도달할 수 있는 상태들을 그래프 구조로 표현하여 확인) 
  • 퍼즐 / 게임 문제 해결 등

 

+ 그래프의 표현 (Graph representation)

• 명시적 표현: 인접 리스트 (Adjacency lists)
  
  • 정점의 개수 |V| 의 크기를 갖는 배열(array) Adj 에 대해, 배열의 각 요소가 연결 리스트(linked list) 의 포인터로 역할하며, 정점에 의해 인덱싱 됨
  • 정점들을 0 에서 |V|-1 까지 레이블! 각 정점이 해시 가능한 무언가 (key) 이고, 배열 Adj 는 해시테이블인 셈!
  • 각 정점 u ∈ V 에 대해, Adj[u] 는 u 의 이웃 정점들을 저장함:  { u∈V | (u, v)∈E }
• 암시적 표현: 함수 (function)
  • Adj(u) 는 함수, v.neighbors() 는 정점 클래스에 대한 메소드로 정의
  • 각 정점에 대한 인접 정점(이웃) 정보를 명시적으로 저장하는 것이 아니라, 필요할 때마다 함수 Adj(u) 를 호출해서 원하는 것을 계산함
  • 함수 Adj(u) 통해 원하는 것을 찾을 때까지만 그래프를 만들어나가면 됨! (그래프 전체를 다 만들 필요가 없을지도...!)  -->  상대적으로 메모리 공간을 덜 차지할 수 있다!
• 명시적 표현을 이용할 경우, 하나의 그래프를 표현하는 데에 O(V+E) 의 공간이 필요함

 

 

* 너비 우선 탐색 (Breath-First Search, BFS)

• 주어진 정점 s 에서 도달할 수 있는 모든 정점들을 탐색하는 것이 목표
• 출발점 s 를 기준으로, 0 번 이동으로 도달 가능한 모든 정점들 -> 1번 이동으로 가능한 모든 정점들 -> 2번 이동 ... -> ... 의 순서로 탐색을 진행!
  • 이전에 이미 방문했던 정점을 다시 방문하지 않도록 (중복을 피하도록!) 주의해야 함 >_<
• [pseudo-code 로 BFS 알고리즘 구현]

def BFS(s, adj):
    level = {s: 0}
    parent = {s: None}
    i = 1           # level indicator
    frontier = [s]  # items of level i-1
    
    while frontier:
        next = []
        for u in frontier:
            for v in adj[u]:
                if v not in level:  # level 이 부여되지 않음 == 이전에 방문한 적이 없음
                    level[v] = i
                    parent[v] = u
                    next.append(v)  # 다음 방문 level 에 해당하는 정점들
        frontier = next  # 해당 level 을 다 방문했으면 다음 level 로 넘어가기
        i += 1

 

• 최단 경로(shortest path): 만약 어떤 정점 v 에 대해 그 부모 parent[v] 를 찾고, 그 부모 parent[parent[v]] ... 를 계속해서 찾아 나간다면 결국 탐색의 시작점이었던 s 에 도달하게 될 것. 이를 역순으로 나열하면 s 에서 v 로 가는 그래프의 최단 경로가 됨!
  • 해당 경로가 유일한(unique) 최단 경로는 아닐 수 있음!
  • 최단 경로는 가장 적은 수의 간선을 사용하는 경로이며, 그 길이는 정점 v 가 갖는 레벨 level[v] 과 같음
• 알고리즘의 총 실행 시간은 O(V+E)
  • 각 정점에 대해 연결된 간선을 한 번씩만 확인하므로, for (v∈V) ∑ | adj[v] | = 2*|E| (무향 그래프) or |E| (유향 그래프)
  • 모든 정점을 방문하는 데에 걸리는 시간 O(V) 가 추가됨