그래프 이론(크루스칼 알고리즘)

크루스칼 알고리즘 (Kruskal Algorithm) 이란 그래프 내의 모든 정점들을 가장 적은 비용(cost)으로 연결하기 위해 사용되는 알고리즘이다.

즉 최소 비용 신장트리를 만들기 위한 대표적인 알고리즘이다.

 

예를 들어 각 도시를 도로를 이용해 연결해 모든 도시가 연결되도록 할 때 최소한의 비용을 구하는 것이다.

 

먼저 신장트리에 대해 알아보자

신장 트리 (Spanning Tree)

이러한 그래프가 있다고  가정하자

이 그래프를 연결하는 최소 연결부분만 사용한다면 아래와 같이 나온다.

 

더 많은 경우가 있지만 생략했다.

• 최소 연결이란 간선의 수가 가장 적다는 것을 의미한다.
• 그래프에서 일부 간선을 선택해서 만든 트리.
• 모든 정점들이 연결 되어 있어야하고 사이클을 포함하면 안된다.
• 하나의 그래프에는 여러개의 신장 트리가 존재할 수 있다.

여기서 간선에 비용이 정해졌을 때 가장 비용이 적은 신장트리를 고르는 것이 최소비용 신장트리이다.

 

 

 

자 이제 크루스칼 알고리즘에 대해 알아보자

이러한 그래프가 있다고 보자 (현재 노드는 6개 간선은 9개인 그래프이다.)

여기서 최소비용 신장트리를 구하는 것이다.

한번 눈대중으로 구해보자.

이게 현재 우리가 구해야하는 최소비용 신장트리이다.

이때 간선은 (노드-1)개가 무조건 나오게 된다.

 

 

어떻게 최소비용트리를 구해야 할까?

 

바로 간선을 거리가 짧은 순으로 그래프에 포함시키면 된다.

 

먼저 모든 노드의 연결된 간선의 정보를 오름차순으로 정렬하고 , 비용이 적은 간선부터 순서대로 그래프에 포함시키면된다.

자 먼저 간선정보들을 오름차순 정렬해보자

이제 이 정보를 이용해서 아래의 알고리즘에 맞게 연결하면 최소비용 신장트리가 나온다.

 

1.정렬된 순서에 맞게 그래프에 포함시키되 포함시키기전에 사이클 테이블을 확인한다.

2. 사이클을 형성하는 경우 간선을 포함하지 않는다.

 

여기서 중요한 점은 사이클이 무엇인지이다.

사이클이란 그래프가 서로 연결되어 사이클을 형성하는 경우인데 최소비용신장트리에서는 사이클이 발생하면안된다.

 

이 때 사이클이 발생하는지의 여부는 지난시간에 배운 Union-find 서로소집합 알고리즘을 적용하면 된다.

 

바로 한번 시작해보자

 

첫번째 간선부터 시작하면 아래와 같이 형성된다.

 

두 번째 간선이다.

 

세 번째 간선이다.

 

 

네 번째 간선이다,

다섯번째 간선이다.

이 때 2 - 4를 연결하게 되면 2 - 3 - 4 가 사이클이 형성된다. 

findParent를 통해 서로 연결됐는지 확인하면 사이클 테이블은 바뀌어

2는 부모값 1

4는 부모값 1로 바뀌게된다.

그래서 두 사이클의 값이 같으므로 사이클형성을  뜻하게 된다.

 

그리고 사이클을 확인하면서 사이클 테이블도 바뀌게된다.

 

 

여섯 번째 간선이다. 완성이 되어 뒤의 간선정보들은 무시를 하면된다.

왜냐하면 모든 간선의 정보를 돌아도 사이클 테이블을 통해 막히게 된다.(이 때사이클 테이블은 모두 1이된다.)

 

예제를 살펴보면서 코드를 보자

 

문제 설명
n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

제한 사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i][1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i][2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

ncostsreturn

4

[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]

4

입출력 예 설명
costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

function solution(n, costs) {
    let answer = 0;
    const parent = [];
    for(let i=0; i<n; i++) parent.push(i); //사이클 테이블 선언
    
    costs.sort((a,b)=>a[2]-b[2]); //간선의 정보 정렬
     
    const getParent = (parent, x) => { //사이클테이블 정보 가져오기
        if(parent[x] === x) return x;
        return parent[x] = getParent(parent,parent[x]);
    }
    
    const unionParent = (parent, x, y) => { //사이클 테이블 합쳐주기
        const n1 = getParent(parent,x);
        const n2 = getParent(parent,y);
        if(n1<n2) return parent[n2] = n1;
        else return parent[n1] = n2;
    }
    //사이클이 발생하는지 안하는지 확인하는 함수
    const findParent = (parent, x, y) => { //사이클테이블에서 두 값의 부모값이 같은지 확인하기
        const n1 = getParent(parent,x);
        const n2 = getParent(parent,y);
        if(n1===n2) return true;
        else return false;
    }
    
    for(const cost of costs){ //모든 간선의 정보를 돌면서
        if(!findParent(parent,cost[0],cost[1])){ //사이클이 발생하지 않는 경우에만 그래프에 포함
            answer += cost[2]; //간선의 비용을 누적한다.
            unionParent(parent,cost[0],cost[1]); //해당 간선을 사이클 테이블을 통해 합쳐준다.
        }
    }
    return answer;
}

 

 

출처

 

https://blog.naver.com/ndb796/221233560789

19. 이진 트리의 구현과 순회(Traversal) 방식