[MIT 6.006 정리] Lec 14. 그래프 (깊이 우선 탐색 (DFS), 간선 분류, 순환 검출, 위상 정렬)

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

 

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

 

* 인접 리스트 & 너비 우선 탐색 Recap

• 인접 리스트(adjacency list)
  • 그래프 구조의 데이터를 나타내기 위해 사용되는 입력(input) 형태
  • Adj[u] = { v ∈ V | (u, v) ∈ E }
  • 배열의 각 인덱스는 각 정점에 매칭되어 (O(V)), 해당 정점에 인접한 정점들(neighbors) 을 리스트(linked list) 형태로 (O(E)) 저장하여 알려줌
• 너비 우선 탐색
  • 모든 정점을 어떤 순서대로 방문하되, 각 정점을 한 번씩만 방문하게 하는 탐색 알고리즘의 하나
  • 그래프의 각 레이어(layer, level) 단위로 차례차례 방문하므로, 시작점 s 에서 특정 정점까지의 최단 경로를 알고자 할 때 유용!
  • 만약 시작점 s 에서 특정 정점을 방문할 수 없다면, 최단 경로는 무한대가 됨 == 방문할 수 없음! 
    -->  이를 이용해서 s 에서 도달할 수 없는 정점을 확인할 수 있음

 

* 깊이 우선 탐색 (Depth-First Search, DFS)

• 그래프를 재귀적으로(recursively) 탐색하되, 필요할 경우 이전으로 되돌아가며 (backtracking) 탐색하는 알고리즘
• [DFS pseudo-code]

parent = {s: None}
def DFS_Visit(adj, s):
    for v in adj[s]:
        if v not in parent:
            parent[v] = s
            DFS_Visit(adj, v)
            
def DFS(V, adj):
    parent = {}
    for s in V:
        if s not in parent:
            parent[s] = None
            DFS_Visit(adj, s)

• 어디서부터 탐색을 시작해야 할 지 모르는 상태에서는, 탐색을 시작할 만한 모든 곳(정점) 을 찾아 탐색을 시도.
  • 해당 정점에서 시작하여 재귀적으로 방문할 수 있는 모든 정점을 방문하되, 이미 방문한 정점은 방문하지 않음!
  • 방문 완료한 정점은 parent(dictonary) 에 해당 정점의 parent 노드와 함께 기록!
• 알고리즘의 총 소요 시간은 O(V + E) (선형 시간! = size of input)
  • 탐색의 시작점으로서 각 정점을 한 번씩 방문 (함수 DFS_Visit 에서의 재귀를 고려하지 않고 DFS 만 고려)
  • 재귀적으로 방문 시, 각 정점을 중복하여 방문하지 않으므로 각 정점 당 함수 DFS_Visit 이 한 번씩 호출됨 
    -->  정점 당 일정 시간 + 재귀 호출 시간만큼 소요! 
    ==  모든 정점의 인접 리스트 길이에 대한 합계  O( ∑_(v∈V) |adj[v]| ) = O(E) (유향 그래프) or O(2E) (무향 그래프)
• 최단 경로 탐색에는 적합하지 않음...! 대신 그래프의 모든 간선을 방문하므로, 간선 분류(Edge classification) 에 유용하게 사용될 수 있음!

 

* 간선 분류 (Edge Classification) 

• 간선의 특성에 따라, 곧 해당 간선을 따라 정점을 방문했을 때 어떤 일이 벌어질 것인가... 에 따라 여러 범주로 분류 가능
  • 트리 간선 (tree edge): 이전에 방문되지 않은 새로운 정점으로 인도하는 간선 (== parent pointer 에 해당!)
    • 트리 간선들은 유향 트리(directed tree) 를 이루게 됨
  • 순방향 간선 (forward edge): 어떤 정점에서 트리의 자손(descendant) 으로 가는 간선
  • 역방향 간선 (backward edge): 어떤 정점에서 트리의 조상(ancestor) 으로 가는 간선 
  • 교차 간선 (cross edge): 선조 관계가 아닌 두 하위 트리 또는 정점 사이의 간선
• 단, 무향 그래프(undirected graph) 의 경우, 트리 간선 & 역방향 간선* 만 존재 가능
• 간선 분류는 아래 두 가지 문제를 푸는 데에 유용하게 활용될 수 있음: 1) 순환 검출(cycle detection) & 2) 위상 정렬(topological sort)

 

* 순환 검출 (Cycle Detection)

• 해당 그래프에 순환(cycle) 하는 경로가 있는지 알아보는 것!
  • 그래프 G 에 순환이 존재함  ==  깊이 우선 탐색(DFS) 에서 역방향 간선(backward edge) 이 존재함
  • ==>  역방향 간선이 있으면 해당 그래프에는 순환이 존재하므로, 역방향 간선이 있음을 보이면 됨!

 

* 위상 정렬 (Topological sort)

• 그래프를 위상(topology) 으로 생각하고, 그래프의 정점을 특정 순서로 정렬하는 알고리즘 
  • 숫자(numbers) 를 정렬하는 것이 아니라 그래프의 정점을 정렬하는 것이라 위상 정렬이라고 함...!!
• 잡 스케쥴링 (Job Scheduling) 문제를 해결하는 데에 활용 가능
  • 비순환 유향 그래프(Directed Acyclic Graph, DAG) 가 주어졌을 때, 모든 간선이 낮은 레벨(lower order) 에서 높은 레벨(higher order) 을 가리키도록 정점들의 순서를 정하는 태스크
  • 예시: 옷 입는 순서 정하기 (속옷 위에 겉옷을 입어야 하는 조건 등을 위배하지 않으면서 순서를 정해야 함..!)
• 일단 깊이 우선 탐색(DFS) 을 실행하고, 방문을 끝낸 정점들을 역순으로 (reverse of finishing time of vertices) 리턴함
  • 상위 DFS 알고리즘 상에서, 한 정점을 끝낼 때마다 리스트에 추가함 & 뒤집기