MST (Minimum Spanning Tree)

Minimum Spanning Tree를 C++ 코드로 짜려고 찾다가 한국어로 잘 소개해 준 페이지를 발견했다.

친절한 블로거다. 나도 뭔가 설명할 때 저렇게 친절하게 해야 하는구나 싶었다. 

일단은 링크를 걸어둔다.

http://findfun.tistory.com/385

알고리즘에 대한 설며도 ppt파일에 굉장히 자세히 나와 있어서 보고 바로 코드를 짤 수 있을 것 같다. 

나중에 완성 되면 올려야겠다.. ㅎㅎ

===============================================================

코드와 설명을 올립니다. 

network의 기본 골격이 어떤 모양인지를 알고 싶어서 weighted network에서 MST를 만들고 싶어졌습니다. 

일단 먼저 MST에 대해서 간략히 소개하겠습니다.

MST는 아래 그림[출처: http://findfun.tistory.com/385]과 같이  네트워크가 있을 때 모든 노드를  트리구조로 이으면서 weight의 합을 최소로 만드는 구조를 말합니다. 

예를 들면, 각 노드 사이에 다리를 지어야 하는데 건설비용이 weight만큼 든다고 할 때 츠리구조로 모든노드가 한 컴포넌트에 들어가게 하면서 가장 적게 돈을  쓰는 방법이라고 할 수 있겠죠. 

더 자세한 설명은 http://findfun.tistory.com/385를 참고하시기 바랍니다. 

물론 경우에 따라 weight의 합이 maximum을 주는 tree를 찾고 싶은 경우도 있을 수 있습니다. 

찾아보니 Python에서 Networkx 패키지를 이용하면 쉽게 MST를 얻을 수 있더군요.

저는 c++ code로 짜고 싶어서 algorithm을 찾아봤습니다. 

MST를 만들 때는 크게 두 가지 알고리즘을 사용하는요.

하나는 프림 알고리즘(https://ko.wikipedia.org/wiki/%ED%94%84%EB%A6%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98) 이고 

다른 하나는 크러스컬 알고리즘(https://ko.wikipedia.org/wiki/%ED%81%AC%EB%9F%AC%EC%8A%A4%EC%BB%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)입니다. 

두 알고리즘 모두 알고리즘 속도가 비슷해서 저는 프림 알고리을 구현 해봤구요.

인터넷에 누군가가 만들어서 배포한 코드도 있긴 합니다.

http://www.sanfoundry.com/cpp-program-find-mst-prims-algorithm/

그냥 저는 제가 한 번 짜보고 싶어서 만들었습니다. 

알고리즘 설명은 wiki 예제로 나와있는게 제일 이해가 잘 되더라구요.

이하 알고리즘 설명은 생략합니다... ㅋㅋ

저는 Maximum Spanning Tree를 만드는 코드를 짰구요, 

in과 out이라는 array를 이용했습니다. 

in에는 MST에 들어가 있는 노드를 out에는 MST에 속하지 않은 노드들을 넣었습니다.

그래서 맨처음에 모든 노드를 out에 넣어두구요.

각 array의 크기를 idxin과 idxout으로 표현했습니다. 

그래서 in으로 하나씩 노드가 들어갈 때마다 idxin과 idxout이 update되구요.

알고리즘은 간단합니다.

in에 있는 노드들과 out에 있는 node들 사이의 link중 weight가 가장 큰 걸 선택합니다. 

그리고 연결시킨다음에 연결된 node는 out에서 in으로 넣어주구요... ㅎㅎ

모든 노드를 다 MST에 넣을때까지 계속해주면 됩니다.

계산시간에 대한 optimize를 한 건 아니라서 패키지가 더 빠를수도 있습니다. 

궁금한 거 있으면 물어보셔요 ㅎㅎ. 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

idxin = 0;idxout = index; in[idxin++] = out[0]; idxout -= 1; out[0] = out[idxout]; while(idxout) {     //find maximum weight link betwwen in and out nodes     node1=0;node2=0;max=0;     for(int j=0; j<idxin ; j++)     {         for(int k=0; k<idxout; k++)         {             if(max < A[in[j]][out[k]] + A[out[k]][in[j]])             {                 max = A[in[j]][out[k]] + A[out[k]][in[j]];                 node1 = j;                  node2 = k;             }         }     }     //update     links[idxin-1][0] = in[node1];     links[idxin-1][1] = out[node2];     links[idxin-1][2] = max;     in[idxin++] = out[node2];     idxout -= 1;     out[node2] = out[idxout]; }