[알고리즘] 크루스칼

[크루스칼 알고리즘]

• 최소신장트리 문제 해결 시 사용
• 간선의 갯수 = 노드의 갯수 - 1

[문제 해결 방법]

1. 비용이 적은 순서대로 오름차순으로 정렬 후 순서대로 이어나간다

    // 비용 작은 순서대로 정렬
    costs.sort((a,b)=>a[2]-b[2]);

2. Union-Find에 따라 각 노드의 부모가 누구인지 찾아주고 연결 후 작은 수의 부모로 통일해준다.

	//Union-Find
	//부모가 자기자신을 가르키도록 초기화
    for(let i =0; i<parent.length; i++){
        parent[i] = i;
    }
    //부모가 누구인지 찾기
    const getParent = (x)=>{
        if(parent[x] === x) return x;
        return getParent(parent[x]);
    }
    //연결지었다면 부모를 통일시켜주기(단, 작은 수로)
    const unionParent = (a,b)=>{
        a = getParent(a);
        b = getParent(b);
        if(a>b) parent[a] = b;
        else parent[b] = a;
    }
    //각 노드의 부모를 찾기
    const findParent = (a,b) =>{
        a = getParent(a);
        b = getParent(b);
        if(a===b) return 1;
        else return 0;
    }

3. 사이클이 연결되지 않도록 하는 것이 중요! => 사이클이 형성되는 경우 간선에 포함시키지 않는다.
   즉, 각 노드의 부모가 같다면 이미 연결된 것이기 때문에 이에 해당하는 조건을 걸어준다.
   +) 종료조건은 간선의 갯수가 노드의 갯수-1이 되는 것이지만 위 조건에 맞지 않으면 어짜피 실행하지 않기 때문에 넣지 않아도 상관없다.

  costs.map((e)=>{
          if(!findParent(e[0], e[1])){
              unionParent(e[0],e[1]);
              cost += e[2];
          }      
      })

블로그에 정리된 크루스칼-유니온파인드를 읽었을 때 이해가 안된다면 유튜브에 나동빈님의 이론 설명 영상을 듣는 것을 강력 추천합니다~!!!!!