[ 알고리즘 ] Graph Traversal : Any-Order Traversal

1. Traversal

 

Traversal : 그래프의 노드를 방문하는 방법

어디서 시작하는지 정하지 않는다. 어디에서 시작하느냐에 따라서 다른 알고리즘이 된다.

 

같은 노드를 여러번 지나갈 수 있다.

어떤 문제를 푸느냐에 따라서 계산할 것들이 달라진다.

 

Traversal을 통해 그래프 안에 뭔가 구조가 만들어질 것이다.

=> 보통 Tree가 만들어 진다.

 

2. Any-Order Traversal

 

어떤 노드 s에서 시작하고 s를 BOX에 넣는다.

BOX가 비어있지 않으면 아래의 과정을 반복한다.

하나의 노드를 꺼내고 방문하지 않은 노드라면 방문한 뒤 어떤 계산을 수행한다.

그리고 노드와 인접한 모든 엣지들을 BOX에 넣는다. 이후 이 과정을 계속 반복한다. 

 

박스에 여러개 들어있다면 어느 것을 꺼내겠는가?

어느 노드를 꺼내느냐에 따라서 건드리는 노드의 순서가 달라진다.

 

2.1 proof

 

AnyOrder Traversal이 Reachable한 노드는 모두 방문한다는 것을 증명하자.

 

Reachable의 의미는 시작 노드 S와 목적 노드 t가 있을 때

S-a1-a2-a3-...-ak-t 가 존재한다는 의미이다.

 

 s에서 t로 가는 길이 있으면 있고 없으면 없다고 하는것을 증명할 것이다.

 

1.먼저 s에서t로 가는 길이 있다면 답으로 check한다는 것을 증명해보자

귀류법으로 증명해보겠다.

1답이 있을때 없다고 하는 상황을 가정해보자.

ai-1  - ai 이렇게 노드가 있고  ai-1까지만 방문해서 목적지까지 방문할 수 없다고 가정해보자.

ai-1이 mark가 되었다면 ai은 Box에 들어간다. 

ai가 Box에 들어들다면 알고리즘에 의해  marking된다 -> 모순

 

2. 체크되어있는것은 답이라는 것을 증명해보자

 

marking되어있다는 것은 한 노드에 인접되어있다는 의미이다.

모든 marked노드는 박스에 넣게 한 원인 노드가 있다.

각자의 원인 노드를 찾다보면 시작 노드가 나오게 될 것이다. 

 

 

2.2. Connected Component

 

덩어리가 생기는 노드는 어떤 노드에서 시작해도 덩어리가 생긴다. 

reachable하다는 것은 즉 path가 있다는 것이고 이는, 같은 덩어리 (component) 안에 있다는 것을 알 수 있다.

 

2.3 Complexity

보통 처럼 노드의 개수 n개 엣지의 개수 m개라고 하겠다

 

1. 박스에서 노드를 꺼낸다  O(m) , 한 노드당 두번씩 호출돼서 2m번 실행

2. 노드가 마킹되어있지 않다면 O(m), 아래과정 m번 실행

1. 노드를 마킹한다 O(1)
2. 주어진 계산을 한다  ?? , 어떤 계산이냐에 따라 다름
3. 인접한 노드들을 박스에 넣는다 ??, 박스 구현 방법에 따라 다름

 

2.4. Event Queue 

이벤트 큐는 그냥 큐와 동일하지만

이벤크를 담고있다고 하면 더 이해하기가 쉬움