[Graph Traversal] Any-order Traversal & Connected Component & Event Queue & RDFS

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

 

결과적으로 어떤 "정보"가 나오게 된다

 

Any-Order traversal

• Start at a Node s (put s into BOX)
• While BOX is not Empty
  • take one node from BOX
  • If Node not Marked -> Mark Node -> Do Computation on Node -> Put Every Adjacent Node into BOX

어떤 것을 하고싶은지에 따라서 달라질 수 있다.

box에 뭘 넣고, 어떤 것을 꺼내는지 등에 따라 달라진다 

 

이 방법으로 Reachability 문제를 풀 수 있다.

Reachability 

Reachability

• Is Node t reachable from s?
• Also, Is there a Path from s to t?

Solution

• Start at s and do Any-Order Traversal
• After Traversal see if t is marked
• 인접한 것은 다 집어넣기 때문에 갈 수 있는 곳은 다 간다

Proof

Any-Order Traversal이 Reachable인 node는 (그것들만) 모두 mark 한다.

 

1. Reachable한 노드를 모두 mark 한다

t가 s에서 reachable <=> t = s or s,a1,a2,a3 ... t라는 sequence 가 있어서 s-a1, a1-a2, a2-a3 ... ak-t가 모두 adjacent(인접)한다

 

귀류법을 사용합시다

 

Assume t is not marked (traversal 후에)

s는 마킹이 되어있지만 t는 마킹이 되어있지 않음

sequence를 따라가다 보면 "처음으로 마킹이 되지 않은 노드"가 존재할 것이다.

처음으로 마킹이 되지 않은 노드를 ai or t라고 하자

ai-1은 마킹이 되어있고 ai는 마킹이 되어있지 않은 것이다

 

알고리즘을 보면 모든 인접한 노드를 박스에 집어넣음

따라서 ai는 box에 들어가게 된다 -> 박스가 빌 때까지 돌기 때문에 무조건 box에서 꺼내지게 된다 -> 박스에서 꺼내지면 mark 된 것

즉, s는 마킹이 되어있지만 ai가 마킹이 되어있지 않다는 것은 절대 불가능하다

따라서 reachable 한 것은 모두 마킹한다.

 

2. Reachable 한 것만 mark한다

invariant : box에 들어가는 node는 모두 reachable

 

Connected Component

Repeat Any-Order Traversal with unmarked Nodes

노드의 집합인데 모든 쌍이 연결되어 있고, 노드를 더 이상 추가할 수 없는 것

 

아무곳에서나 Traversal을 해서 reachable 한 것은 모두 마크가 된다

아직 mark가 되지 않은 노드는 다시 traversal해서 connected component를 찾으면 된다

 

Time Complexity

node : n

edge : m

• start at a Node s (put s into Box)
• While BOX is not Empty
  • Take one Node from Box (한 노드가 박스에 몇 번 들어가는가? : 모든 노드가 인접한 edge 갯수만큼 들어감) -> O(m)번
  • If Node not marked -> O(m)번
    • Mark node -> O(1)번
    • do computation on node -> x*
    • Put Every Adjacent Node into Box (박스에 몇번 들어가는지와 같음)
    • 총 시간은 O(n)

O(box구현에 의존 x m + x* + n)

 

box 구현에 의존하는 부분은 box를 어떻게 구현하느냐에 따라서 꺼내는데에 걸리는 시간이다

 

Event Queue

독립적인 이야기이다.

하지만 이러한 event queue는 box를 만드는 방법 중 하나이다

 

감염이 퍼저나간다.

어떠한 격자칸이 있고, 그 일부는 이미 감염이 되어있다.

감염이 되어있지 않은 격자칸이 감염이 되는 규칙은 상하좌우 4개 중 2개 이상이 감염이 되어있을 때이다.

 

격자 칸의 크기는 n x m

느린 alg : 매 round 마다 모든 칸 확인 -> 시간 O(kmn) / k : total round 수

빠른 alg : event queue

 

특정한 칸이 5번째에 감염이 되었다고 가정해보자.

그렇다면 6번째에 감염될 수 있는 가능성이 해당 칸을 기준으로 상하좌우에 생기게 된다.

(이미 감염되어있는 것은 무시하면 됨)

반대로 생각해보자

5번째에서 감염이 되지 않았다고 가정해볼 때, 6번째에서 감염이 될 가능성을 생각해보자.

내가 6번째에서 감염이 될 가능성이 존재하기 위해서는 상하좌우 중 한 곳에서 5번째에 감염이 되었어야한다.

그 이유는, 그 이전에 감염이 되었다면 이미 감염이 되어있어야하고 감염이 되지 않으면 감염이 발생하지 않음

 

새로운 감염이 발생할 수 있는 가능성이 생겼다는 event가 발생하는 것이다. 

따라서 event queue에 집어 넣는 방식으로 하면, 

event queue에 있는 칸만 확인하여 매 라운드에 걸리는 시간이 달라진다.

 

그럼 각 box가 event queue에 몇번씩 들어가는가? -> 4번

 

빠른 alg : 한 칸은 queue에 최대 4번 -> queue에서 꺼내면 O(1) -> O(mn)

 

What Kind of Box?

• Stack -> DFS
• Queue -> BFS
• Priority Queue
  • With edge weight -> Prim
  • With distance from s -> Dijkstra (edge weight가 1인것이 BFS)
  • Arbitrary Function -> A*

 

Recursive DFS

• RDFS (Node s)
  • Mark Node s
  • Set Pre(s) : 노드에 들어왔을 때 하는 계산 -> O(1)
  • For every adjacent node t : 중간에 갈 수 있는 곳을 전부 감
    • if t is not marked RDFS(t) : 인접한 노드에 대해서 마킹이 되어있지 않으면 재귀 호출을 한다
  • Set Post(s) : 노드에서 떠날 대 하는 계산 -> O(1)

 

전진할 수 있는 노드가 있으면 쭉 전진한다. 

더 이상 전진할 수 있는 노드가 없을 때 back track 한다. 

back track 하다가 전진할 수 있는 노드가 새로 생기면 전진한다.

 

이러한 재귀로 구현을 하면 전체 시간 복잡도를 구해보자

각 노드가 RDFS의 인자가 되는 것은 1번이다. 

붙어있는 edge 갯수만큼 보고, 이를 n번 호출함

O(m+n)이다.

 

Simulate Recursive with Any-Order Traversal

• Start at a Node s (put s into Stack)
• While Stack is not Empty
  • Take one Node p from stack
  • if Node not Marked
    • Mark Node
    • Do computation on Node
    • Put Every Adjacent Node q into Stack

 

재귀 호출하는 것과 비슷하지만, post 하는 과정이 없음

마무리 작업 하는 걸 stack에 하면 되긴 함 (인접하는 노드를 넣기 전에)