알고리즘19 그래프 알고리즘

배열, 기하에 비해 직관적으로 풀기 어렵다.

친구 추천 알고리즘 등에 쓰이는 경우가 많다.

 

체계적으로 만드는 방식 : Graph Traversal

 

---

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

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

 

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

어떤 문제를 푸느냐에 따라서 뭔가를 계산한다.

 

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

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

 

*그래프에서 안풀리는 문제가 트리에서 풀리는 경우가 많다.

 

---

(일반적인 form)

 

노드 s에서 시작한다. (노드 s를 정하는 방법은 문제마다 다르다.)

s를 박스에 넣는다. 박스에 넣는 것은 앞으로 처리할 일들

 

빈 박스가 아닌 동안 프로그램이 돈다.

노드를 박스에서 꺼낸다.

노드가 not marked이면, 마킹&무언가를 계산한다.

인접한 노드들을 박스에 넣는다.

 

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

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

 

---

p, q의 순서는 보통 구분하지 않지만

q가 먼저나왔을때 그 다음에 p가 나올지 a가 나올지는 정한다.

 

---

Reachability : 길이 있냐는 뜻

 

다른 덩어리가 t가 있으면 reachable하지 않은 것

다른 덩어리를 정의해야 한다. (s에서 t까지 path가 있다 / 없다)

 

인접한 노드를 넣으므로 s와 같은 덩어리는 다 가보고 끝나겠지.

 

 

증명)

"s에서 t로 가는 path가 있으면 marking이 되고

marking이 되면 s에서 t로 가는 path가 있다."

 

t가 마킹된다는 것을 증명하기 위해

모든 노드들 중 s에서 shortest path가 길이 k인 것

(k에서 수학적귀납법 하면된다.)

 

base: k=0 s=t 이므로 마킹된다. (s는 무조건 마킹되므로)

step: k에서 성립하면 k+1에서 성립한다.

 

s에서 shortest path의 길이가 k인 모든 노드 p가 마킹이 되면

s에서 shortest path의 길이가 k+1인 모든 노드 q가 마킹이 된다는 것을 보인다.

 

r이 마킹이 되었으면 r과 인접한 노드는 모두 스택에 들어간다.

그러므로 q는 박스에 들어가고 언젠가 마킹된다.

(while문은 박스가 빌때까지 도니까)

 

 

---

반대로

"q가 마킹이 되어있으면 s에서 t로 가는 path가 있다."

 

 

---

비슷한 다른 것을 증명하기

 

모든 marked node는 s에서 t로가는 path가 있다.

 

알고리즘에서 marked되는 것은 패스가 있다는 것을 보일 수 있다.

이미 마크된 노드가 인접한 애를 박스에 넣었다.

이미 마크된 노드 역시 얘를 박스에 넣은 노드가 있을 것.

이런식으로 최초의 s까지 가게 된다.

 

박스에서 꺼낸 순서와 상관없이 직관적으로 reachable알 수 있다. 

---

 

아무노드에서나 시작해도 덩어리생긴다.

* reachable하다 = path가 있다 = 같은 component에 있다

---

 

 

n = | V | , m = | E |

undirected graph G = (V, E) 

Adjacency List

 

입력사이즈 = n+m

 

 

 

start at a Node s => 상수 시간

while{ => 2m번 돈다.

  take one node from Box => log n일수도 있는데 상수시간이라고 치자 (X)

   if(not marked){

     mark node => 알고리즘 전체에서 n번

     인접한 노드를 박스에 넣는다. => 전체에서 2m번

   }

}

 

*한 노드가 박스에 여러번 들어갈 수 있다.

( 모든 노드는 엣지 갯수만큼 박스에 들어간다.)

(엣지마다 양쪽 노드를 한번씩 넣는다.)

 

*한 노드는 한 번 마킹된다.

 

=> O(N + M x X )