[Algorithm] Graph

Graph는 우와 재밌는 거다. 이번 포스팅은 Graph를 설명할 예정이다. 정확히말하면 Graph를 전제로 사용하는 세 개의 아주 유명한 Algorithm을 설명할 생각이다.

Primm's Algorithm

Kruskal's Algorithm

Dijkstra Algorithm

우선 Primm's와 Kruskal's Algorithm을 설명하려면 minimum spanning tree를 알아야 된다. minimum spanning tree는 무엇인가? 아래의 Graph를 보자. 

여러 개의 Node(Vertex라고도 한다.)와 Edge가 있는데, Edge는 cost가 있다. 예를 들어, AB를 잊는 Edge의 Cost는 4이다. 이 Edge cost의 합을 최소한으로 하여 모든 node를 잊는 Tree를 minimum spanning tree라고 한다. 위 Graph에 대한 minimum spanning tree는 아래와 같다.

Primm's와 Kruskal's Algorithm은 모두 어느 그래프의 minimum spanning tree를 찾기 위한 알고리즘으로 당연히 위와 같은 결과를 준다.

Kruskal's Algorithm이 더 간단하기 때문에 이것부터 설명하려한다. 딱 세 개의 단계 밖에 없다.

Step 1: Edge Cost를 sorting을 한다.

Step 2: 가장 작은 Edge들을 잇는다. 이 때, cycle이 생기면 안된다)

Step 3: minimum spanning tree가 완성될 때까지 순서대로 edge를 잇는다.

Primm's Algorithm은 Kruskal's Algorithm과는 다르게 Starting point가 있다. A를 시작점으로 하고 아래의 설명을 읽어보면 된다.

Step 1: A에 연결된 Edge를 비교하여 작은 것을 잇는다. AB=4, AF=10

Step 2: B에 연결된 Edge를 기존의 AF=10과 함께 비교하여 가장 작은 것을 택한다. AF=10, BF=7, BC=5, BD=2 중에서 가장 작은 BD=2를 택한다.

Step 3: D에 연결된 Edge를 기존의 Edge들과 함께 비교한다. 가장 작은 것을 택한다.

Step 4: minimum spanning tree가 완성될 때까지 반복한다.

Kruskal's Algorithm과 Primm's Algorithm은 minimum spanning tree를 찾는 알고리즘인 반면, Dijkstra Algorithm은 Shortest path를 찾는 Algorithm이다. 한 node에서 다른 node로 가는 가장 짧은 길을 찾는 Algorithm이다. 보통 네트워크에서 라우팅을 할 때 쓰이는 것으로 알고 있다. A node에서 시작한다고 가정하고, 위의 Graph에 dijkstra Algorithm을 적용하면 아래의 결과가 나온다.

Dijkstra Algorithm : https://www.youtube.com/watch?v=gdmfOwyQlcI

위의 링크에서 아주 잘 설명해주고 있다. 영어다 -_- 그래도 그림이 있으니 잘 이해할 수 있을 것이다. 우와 일단 Algorithm에서 설명하려고 했던 건 다했다. 이전의 내 포스팅과 비교하면 뭔가 속성이다라는 느낌이 없지않아 있지만, 그래도 계획대로만 된다면 몇 일 후에 포스팅할 data mining쪽은 아주 자세하게 갈 것이다. 그 포스팅은 기대해도 된다.

다음 포스팅은 OOP. Object Oriented Programming이 될 것이다. Java를 기반으로 설명할 생각이다. 프로그래머는 아니지만 그래도 열심히 잘 설명해보리다.