Graph Traversal

그래프는 알고리즘이 돌아가는게 직관적으로 눈에 보이지도 않고 문제가 조금만 복잡해져도 많이 어렵지만 그래프를 풀 수 있어야 한다. 이는 체계적으로 생각하기가 어려워서인데, traversal은 체계적으로 생각할 수 있게 해준다.

Traversal

  • Visit nodes of a graph in some order
    • May go through a node several times
    • While doing some calculation
  • Usually after the traversal some data structure results
    • useful information extracted

traversal은 굉장히 넓은 알고리즘을 뭉뚱그려 말하는 것이다. 어디서 시작하느냐에 따라 다른 알고리즘인데, 보통은 엣지를 따라 노드를 방문하며 계산을 한다.

쉬운 문제는 traversal만 하면 끝날 때도 많은데 어려운 문제는 그래프 안에 부가적인 구조가 있는 경우가 종종 있다. 이때 부가적인 구조는 트리가 많고, 그래프에서 잘 안 풀리는 문제인데 트리에서는 잘 풀리는 경우가 많다.

Any-Order Traversal

  • Start at a node s (put s into a box) // box: 앞으로 처리할 것들을 넣어둔 것
  • While !box.isEmpty
    • Take one node from box // 어떤 노드를 꺼내느냐에 따라 다른 traversal임
    • If !marked(node)
      • Mark node
      • Do computation on node
      • Put every adjacent node into box

This Solves Reachability

  • Reachability
    • Is node t reachable from s?
    • Is there a path from s to t?
  • Solution
    • Start at s and do Any-Order traversal
    • See it t is marked after traversal // box에서 어떤 순서대로 꺼내는지 상관 없음!

Proof

증명할 명제:
s로부터 t까지의 path가 존재하면, traversal 후 t는 mark된다.

Idea
모든 노드 중 s에서 shortest path가 k인 것들이 마킹된다는 것을 증명한다. 이때 수학적 귀납법을 이용해 모든 k에 대해 증명하면 된다.

Base
k = 0일 때 s == t이므로 성립한다.

Step
k에서 성립한다고 가정하고 k+1에서도 성립함을 보인다.
s로부터 shortest path의 길이가 k인 p(모든 p)가 마킹이 되면, s로부터의 shortest path의 길이가 k+1인 q가 마킹된다는 것을 보이자.

q 바로 앞의 노드를 r이라 하면(s -> r -> q), s ->r의 길이는 k이고 r->q의 길이는 1이므로 q->r의 길이는 k+1이다. 그런데 r은 마킹되었으므로 r과 인접한 모든 노드들도 box에 들어간다. box에 들어가면 언젠가는 box에 꺼내지므로 언젠가는 s도 마킹된다는 것을 알 수 있다.

따라서 모든 k에 대해 성립하므로 path가 존재하면 무조건 마킹된다.

그러면 이제 역도 성립함을 보이자.

증명할 명제:
traversal 후 t는 mark되면, s로부터 t까지의 path가 존재한다.

간접적으로 증명해보자.

간접 증명할 명제: 마킹된 모든 노드 t’는 s로부터 t’로 가는 path가 존재한다.

t’을 box에 넣은 노드를 x라 하면, x의 t’의 인접한 노드이다. 왜냐하면 알고리즘에서는 현재 box에서 꺼낸 노드의 모든 인접한 노드들을 box에 집어넣기 때문이다. 그러면 x는 누가 box에 넣었을까? 이렇게 계속 따라가보면 s에 도달하게 된다.

Connected Component

  • Repeat Any-Order traversal with unmarked nodes

아무 노드에서 시작해 any-order traversal을 하면 reachable한 노드가 다 마킹되기 때문! 그러면 덩어리들이 나옴.

Time Complexity

  • 가정
    • undirected graph G = (V, E)
    • |V| = n, |E| = m
    • Adjacency List:
      • adjacency list로 줘야지 m으로 풀 수 있음. 이차원 배열같은 걸로 주면 m^2에 풀어야 함.
  • Start at a node s (put s into a box) –> 상수 시간
  • While !box.isEmpty –> 2m번 실행
    • Take one node from box –> X시간이 걸린다 가정
    • If !marked(node)
      • Mark node –> 알고리즘 전체를 봤을 때 n번 실행됨
      • Do computation on node
      • Put every adjacent node into box –> 알고리즘 전체를 봤을 때 2m번 실행됨

따라서 O(n + m*X)의 시간이 걸린다.

Event Queue

box가 queue인 경우. event queue로 푸는 문제를 풀어보자

이차원 격자칸이 있다. O로 표시된 칸들은 시작할 때부터 감염된 칸이다.

               
    O          
        O      
    O   O   O  
      O        
               
               

처음 시작할 때 감염된 칸들이 있고, 매 라운드마다 감염이 확산되는데, 인접한 칸들 중 두 개 이상의 칸이 감염돼 있으면 감염된다.

1 라운드 후

               
    O          
    1   O      
    O 1 O 1 O  
    1 O 1      
               
               

2 라운드 후

               
    O          
    1 2 O 2    
    O 1 O 1 O  
    1 O 1 2    
               
               

6 라운드 후

               
    O 3 4 5 6  
    1 2 O 2 3  
    O 1 O 1 O  
    1 O 1 2 3  
               
               

그 이후에는 감염이 더이상 진행되지 않는다. 이때 감염된 칸들을 다 찾는 문제.

진짜 다 구하면 되긴 하는데, 그러면 round 수 X n(행) X m(열)의 시간이 걸린다(너무 오래 걸림).

대신 event queue를 만들어보자.

초기 상태에서 전체를 흝으며 감염된 칸들을 큐에 집어넣는다. (감염이 전파되는 event들을 넣어놔서 event queue임).

그러면 첫 번째 라운드에서 생긴 감염 때문에 추가로 감염되는 칸이 생기고, 추가 감염의 가능성이 있는 칸은 감염된 칸의 상하좌우 네 군데 뿐이다.

첫 번째 라운드에서 감염 가능성이 있는 칸들로 인하여 두 번째 라운드에서 감염될 칸들을 알 수 있을 뿐만 아니라 첫 번째 라운드에서 감염된 칸의 인접한 네 칸에 대해서만 확인하면 된다.

Time Complexity

초기 상태에서 모든 칸을 보고 O(nm), 감염이 일어날 때마다 감염된 칸의 인접한 네 칸을 본다 O(nm X 5). 따라서 전체 O(nm)의 시간복잡도를 가진다.

What Kind of Box?

  • Stack -> DFS (Depth-First Search)
  • Queue -> BFS (Breadth-First Search)
  • Priority Queue: box에 node랑 다른 값도 추가로 집어는데, 추가로 집어넣는 값이
    • With edge weight -> Prim
    • With distance from s -> Dijkstra
    • Arbitrary function -> A*

자세한 내용은 다음에~ 👋🏻