구현 - 프림 알고리즘

출처 - C++로 쉽게 풀어쓴 자료구조

개념 자체는 이해하기는 쉬운데, 코드가 이해가 안되서 오래 봤음. 책의 코드 설명이 좀 어렵게 느껴진다.

스스로의 이해를 위해 설명해보자면 딱 정점 수 만큼 루프를 도는데, 루프 한 단계마다 현재까지 알려진 정점 중 가장 가까운 점을 찾아가고, 찾아간 점은 selected에 기록을 한 후, 찾아간 점에서 또 정점 수 만큼 루프를 돌면서 (이중루프) !selected인 주변 점의 정보를 dist에 갱신하는 것이다.

즉 dist[i]는 현재까지 추가한 모든 점중 하나로부터 점 i까지의 최단거리를 담은 정보다. 이 점 i까지의 거리가 다른 추가되지 않은 점과의 거리중 가장 짧으면 i는 (!selected라면)다음 점으로 추가되는 것이다. 점을 추가해가면서 정보는 갱신될 수도 있고 아닐 수도 있다. 

시간복잡도는 그냥 봐도 O(n^2)인 것 같다.

밑은 변수명을 제외하면 거의 책코드 그대로

getMinVtxIdx()

 이 함수는 뭐라고 이름 짓는게 좋을까?

책에는 getMinVertex 라 되어있는데 이건 index가 아닌 정점을 반환하는 거 같아서 맘에 안든다.

get_min_vertex_index ? getMinVertexIndex ? get_min_vtx_idx ? min_vtx_idx ? get은 프로퍼티같앙..

#include "WGraph.h"
using namespace std;
 
class WGraphMST : public WGraph
{
public:
 
    int getMinVtxIdx(bool selected[], int dist[])
    {
        int minVertexIndex = 0;
        int mindist = INF;
        for (int i = 0; i< size; ++i)
        {
            if (!selected[i] && dist[i] < mindist)
            {
                mindist = dist[i];
                minVertexIndex = i;
            }
        }
        return minVertexIndex;
 
    }
 
    void Prim(int s)
    {
        cout << "Prim : \n";
        bool selected[MAX_VTXS];
        int dist[MAX_VTXS];
        for (int i = 0; i < size; ++i)
        {
            dist[i] = INF;
            selected[i] = false;
        }
        dist[s] = 0;
 
 
        for (int i = 0; i < size; ++i)
        {
            int u= getMinVtxIdx(selected, dist);
            selected[u] = true;
            if (dist[u] == INF) return;
 
            cout << getVertexName(u) << " ";
 
            for (int v = 0; v < size; ++v)
                if (getEdge(u, v) != INF)
                    if (!selected[v] && getEdge(u, v) < dist[v])
                        dist[v] = getEdge(u, v);
 
        }
        cout << endl;
    }
 
};