[Lecture] Graph Traversal

특정 노드(x) 하나가 없어지면, 그래프가 끊어질 때, 특정 노드(x)를 구하는 방법은 무엇일까?
 
방향이 없으면 힘들어진다
다익스트라는 소스에서 가까운 것부터 방향을 만들어가면서 해결한다
보통 방향을 정한 다음에 늘려가면서 구한다
local과 global 정보가 섞여 들어오면서 문제를 풀게된다
 
다익스트라에선 빨간색이 최종답이었다
위 그림에서 30 입장으로 인접한 노드들을 바라봤을 때, 35,38,40이라는 정보를(local)알 수 있다
global 정보는 파란 것 중에서 가장 작은 것을 뽑는 것이다
global정보가 간단할수록 쉽게 풀린다
다익스트라는 traversal로 볼 수 있다
 

Traversal

어떤 순서에 따라 그래프의 노드를 방문한다
일반적으로, 해당 노드에서 연산을 하면 방문했다고 표현하고, 지나가면 방문하지 않았다고 한다
 
traversal 후에 어떤 data structure가 결과가된다
다이스트라도 결국 tree를 만든다
트리는 root부터 어떤 노드까지 방향을 가지고 있다
 

Any-Order Traversal

Start at a Node s (Put s into BOX)
While Box가 Empty일 때까지
* Box에서 어떤 기준으로 하나를 뽑는다
* 노드가 Marked되어있지 않다면
   - 노드를 마크한다
   - 노드안에서 작업한다(계산한다)
   - Box에 인접한 모든 노드를 넣는다 (중복이 있을 수 있다)
 
이것만 가지고 Reachability를 해결할 수 있다
다익스트라를 돌리고, Path의 길이가 문한대가 아니면, 길이 있다는 것이다
 

Reachability

노드 t가 s에 도달했는가?
또한 a path는 s에서 t로 가는 경로인가?
 

Solution

s부터 시작해서 Any-Order Traversal을 수행한다
Traversal후에 t가 marked되었는지 확인한다
 

증명

1. 길이 있으면 항상 marked되어있다
2. 길이 없으면 marked되어있지 않다
 
1)
mark하다가 marked가 안된 노드를 만날 경우
인접한 노드를 다 넣고 비어있지 않으면 해당 노드를 marked하기 때문에, 모순된다
 
2)
mark가 되어있으면 길이 있다(대우)로 증명한다
(증명을 어떻게 했더라)
 
위 그림에서 maximal(극대) connected grapth 를 구하라고 했을 때, 주황색 부분은 connected grapth가 아니다. 
maximal은 더 이상 키울 수 없는 이라는 뜻을 가지고 있다
maximal(극대) vs maximum(최대)
 
덩어리가 몇개로 나눠져있는지 어떻게 확인할까?
traversal을 몇번 돌린다 = component를 찾을 수 있다
 
While Box가 Empty일 때까지
* Box에서 어떤 기준으로 하나를 뽑는다 (   )
* 노드가 Marked되어있지 않다면 (상수시간)
   - 노드를 마크한다 (상수시간)
   - 노드안에서 작업한다(계산한다) (    )
   - Box에 인접한 모든 노드를 넣는다 (중복이 있을 수 있다) = (최대 2m)
 
따라서, 
 
While Box가 Empty일 때까지 (2m)
* Box에서 어떤 기준으로 하나를 뽑는다 (   )* (2m)
* 노드가 Marked되어있지 않다면 (상수시간)
   - 노드를 마크한다 (상수시간)
   - 노드안에서 작업한다(계산한다) (    )*n 
   - Box에 인접한 모든 노드를 넣는다 (중복이 있을 수 있다) = (최대 2m)
 

Event Queue

ex) 다익스트라 메세지 개념
감염된 칸이 위, 아래, 좌, 우로 퍼진다
4개 중 2개 감염 시 나도 감염된다
감염속도를 맞추는 것은 좀 더 어려운 문제이다
 
마지막에 어떤 칸이 칠해져있을까?
한개씩 traversal하면 (mn)^2이 나온다
 
큐를이용한다 - 감염 안된 것을 넣고(순서는 중요하지 않다) 하나씩 감염시키고 주변을 살핀다(위 아래 좌 우)
그럼 mn + mn(마지막 확인) = 2mn의 시간이 걸린다
 
Box의 종류
Stack - DFS
Queue - BFS
Priority Queue
with edge weight = prim
with distance from s = Dijkstra
Arbitrary Function = A* (나머지 온갖 복잡한 것 모두를 아우른다)
 
Recursive DFS
RDFS(Node s)
* Mark Node s
* Set Pre(s)
* For every adjacent node t
      If t is not marked RDFS(t)
* Set Post(s)
 
위 순서대로 해야하는 이유 : !!!!
재귀는 어떤 노드를 언제 부를지 모르기 때문에 결과가 여러가지이다 (그럼에도 신기하게 답이 나오는 것임)
재귀가 stack보다 좀 느리다 
사실 재귀도 call stack을 쓴다
 
DFS Tree
 

Back Edges

= foward edge
나머지 edge라는 뜻이 아니다
해당 노드에서 호출 뒤를 쳐다봐서 보고, 노드를 추가하지 않고 Back하는 것
 

Bipartite Graph Detection

입력그래프가 B-G인지 확인한다
L R로 나뉘는게 하나라도 있으면 B - G이다 (평면그래프와 유사)
DFS로 하면 한번으로 확인이 가능하다 (위 그림 참조)