[Level2][Javascript] 섬 연결하기

//minimum spanning tree problem

function solution(n, costs) {
    var answer = 0;
    let visited={};
    if(n===1) return 0;
    costs.sort(function(a,b){
    return a[2]-b[2]; 
    })
    // console.log(costs);
    
    visited [costs[0][0]]=1;
    visited [costs[0][1]]=1;
    answer+= costs[0][2];
    costs.shift();
    while( Object.keys(visited).length!==n){
        for(let index=0; index<costs.length;index++){
            let e= costs[index];
        if(visited[e[0]]===1 && visited[e[1]]===1){
        // console.log("IGNORE");
        }
        else{
        if(visited [e[0]]===1){
            visited[e[1]]=1;
            answer+=e[2];
            costs.splice(index,1)
            break;
        }
        else if(visited [e[1]]===1){
            visited[e[0]]=1;
            answer+=e[2];
            costs.splice(index,1)
            break;
        }
        }
    }
    }
    return answer;
}

최소 신장 트리이다. 

최소 신장 트리 알고리즘은 프림, 크루스칼이 존재하는데, 

프림은 한번 edge를 결정하면 무조건 spanning tree의 일부분이 된다. 하지만 kruskal의 경우 edge가 추가된 이후, acyclic한지 검증해본다. 이를 n-1번 반복하는 것을 목표로 한다. 

 

간선의 수가 적은 경우 크루스칼이 유리하고, 간선의 수가 많은 경우 프림이 유리하다. 

크루스칼 O(E log V);

프림=> binary Heap구현시 O(E log V); -> heap 자료구조상 빠르게 접근 가능하니까

unsorted array O(V^2)

 

/*/프림과 크루스칼 추가적으로 내용 작성 필요.