[알고리즘] 최소신장트리(MST)

|  최소신장트리

- Mininum Spanning Tree

- 그래프의 모든 노드를 연결할 때 가중치 합이 최소가 나오는 트리

- 특징 : 

(1) 사이클 제외 -- 가중치의 합은 사이클이 포함될 때 최소가 될 수 없다. 

(2) N개의 노드에 대한 최소신장트리 간선 수는 늘 N - 1개이다.

 

|  종류

	크루스칼(Kruskal)	프림(Prim)
핵심	- 최소값의 간선 우선 연결 - 사이클 발생 시 다른 간선 선택	- 임의의 노드에서 시작 - 연결된 간선 중 낮은 가중치 선택
언제?	- 간선 수가 비교적 적을 때	- 간선 수가 많을 때 유리
메모리	에지 리스트(or 배열) 유니온 파인드 배열	인접 리스트(or 배열) 방문 배열
속도	O(ElogE)	O(ElogV)  - 우선순위 큐 사용 시 *O(v2) - 정렬되지 않은 배열을 사용할 때

 

|  크루스칼 구현

- 구현 순서

1	에지 리스트(그래프) & 유니온 파인드 배열 초기화
2	에지 리스트를 가중치 기준으로 정렬
3	가중치가 낮은 에지부터 연결하기 반복

 

[1] 에지 리스트(그래프) 정렬 & 유니온 파인드 배열 초기화

- 수업 시간의 경우, 아예 외부에서 입력값으로 미정렬된 간선 배열을 받는 것을 가정으로 했다.

- 이 경우에는 위의 [1][2]를 묶어 간선 배열을 정렬하면 된다.

// 전역변수로 유니온-파인드 배열 지정
static int[] parents;

// data : 간선배열, v : 노드 수, e : 간선 수
public static int kruskal(int[][] data, int v, int e) {
    int weightSum = 0; // 전체 가중치
    
    // 1. 그래프 및 유니온 파인드 배열 초기화
    // 1-1. 그래프 정렬
    Arrays.sort(data);
    
    // 1-2. 유니온 파인트 배열 초기화
    parents = new int[v + 1];
    
    for (int i = 1; i < v + 1; i++){
    	parents[i] = i; // 처음에는 자기 자신
    }
    
    return weightSum;
}

 

[2] 가중치가 낮은 에지부터 연결하기 x 반복

- 가중치가 낮은 에지부터 연결을 하려면 먼저 아래와 같은 메소드가 필요하다.

- 참고로 수업시간에 받은 간선 배열은 무방향 간선들로, 모두 (작은 숫자 노드 -> 큰 숫자 노드)로 연결되어 있었다.

 

2-1. find(int a) :: int 

public static int find(int a){
	// 자기 자신과 연결된 경우
	if (parents[a] == a){
    	return a;
    }
    // 자기 자신과 연결되지 않은 경우
    return parents[a] = find(parents[a]);
}

 

2-2. union(int a, int b) :: void

public static void union(int a, int b){
    int aP = parents[a];
    int bP = parents[b];
    
    if (aP != bP){ // 여기서는 크기비교x (필요할 경우 추가)
    	parents[aP] = bP;
    }
}

 

2-3. 최소값 우선으로 간선 연결

public static int kruskal(int[][] data, int v, int e){
    // 생략
    
    // 2. 최소값 우선 간선 연결
    for (int i = 0; i < e; i++){
    	// 서로 연결된 적이 없었던 경우
        if (find(data[i][0]) != find(data[i][1]){
        	// 연결
            union(data[i][0], data[i][1]);
            // 전체 가중치 값 갱신
            weightSum += data[i][2];
        }
    }
}

 

- 전체 코드

 

static int[] parents;
public static int kruskal(int[][] data, int v, int e) {
    int weightSum = 0;

    // 1. 그래프 및 유니온 파인드 배열 초기화
    // edge graph
    Arrays.sort(data, (x, y) -> x[2] - y[2]);

    // union-find
    parents = new int[v + 1];
    for (int i = 1; i < v + 1; i++) {
        parents[i] = i; // 최초에는 자기자신
    }

    // 2. 최소값 우선으로 간선 연결
    for (int i = 0; i < e; i++) {
        if (find(data[i][0]) != find(data[i][1])) {
            union(data[i][0], data[i][1]);
            weightSum += data[i][2];
        }
    }

    return weightSum;
}

public static void union(int a, int b) {
    int aP = find(a);
    int bP = find(b);

    if (aP != bP) {
        parents[aP] = bP;
    }
}

public static int find(int a) {
    if (a == parents[a]) {
        return a;
    }
    return parents[a] = find(parents[a]);
}

 

|  프림 구현

- 구현 순서

1	인접 리스트 및 방문 배열 초기화
2	우선 순위 큐를 통해 자동 정렬
3	임의의 노드(ex. 1)를 선택한 후 낮은 가중치의 간선 연결 x 노드 수만큼 반복

 

- 원리

입력받은 간선 데이터
int[][] graph = 
{{1, 3, 1}, {1, 2, 9}, {1, 6, 8}, 
{2, 4, 13}, {2, 5, 2}, {2, 6, 7}, 
{3, 4, 12}, 
{4, 7, 17}, {5, 6, 5}, {5, 7, 20}};

 

(1) 방문 배열 : 총 노드의 수(v)만큼 방문배열이 입력된다.

	1	2	3	4	5	6	7
1	t
2	t		t
3	t		t			t
4	t		t		t	t
5	t	t	t		t	t
6	t	t	t	t	t	t
7	t	t	t	t	t	t	t

 

(2) 우선순위 큐

- 가중치의 크기를 기준으로 오름차순 자동 정렬

- 가장 작은 가중치의 노드를 꺼내, 방문 배열을 체크하고, 전체 가중치(weightSum)를 +하는 형태

  * 방문했던 노드는 다시 방문하지 않는다면, 결과적으로는 1-3-6-5-2-4-7 과 같이 노드가 연결될 것

- 타입 : Node (도착노드, 가중치)

흐름	우선순위 큐
초기	N(1, 0)
1	N(3, 1)	N(6, 8)	N(2, 9)
2	N(6, 8)	N(2, 9)	N(4, 12)
3	N(5, 5)	N(2, 7)	N(2, 9)	N(4, 12)
4	N(2, 5)	N(6, 5)	N(2, 7)	N(2, 9)	N(4, 12)
5	N(6, 5)	N(2, 7)	N(2, 9)	N(4, 12)	N(4, 13)
6	N(4, 13)	N(7, 17)

 

- 구현

 

[1] 인접 리스트 및 방문 배열 초기화

static class Node{
    int to;
    int weight;
    
    Node(int to, int weight;){
    	this.to = to;
        this.weight = weight;
    }
}

public static int prim(int[][] data, int v, int e){
    // 인접리스트
    ArrayList<ArrayList<Node>> adjList = new ArrayList();
    for (int i = 0; i < v + 1; i++){
    	adjList.add(new ArrayList());
    }
    
    for (int i = 0; i < e; i++){
    	// 양방향으로 저장
    	adjList.get(data[i][0]).add(new Node(data[i][1], data[i][2]));
        adjList.get(data[i][1]).add(new Node(data[i][0], data[i][2]));
    }
    
    // 방문 배열
    boolean[] visited = new boolean[v + 1];
}

 

[2] 우선 순위 큐를 통해 자동 정렬

public static int prim(int[][] data, int v, int e){
    // 생략
    
    // 우선순위 큐
    PriorityQueue<Node> pq = new PriorityQueue((x, y) -> x.weight - y.weight);
}

 

[3] 임의의 노드(ex. 1)를 선택한 후 낮은 가중치의 간선 연결 x 노드 수만큼 반복

public static int prim(int[][] data, int v, int e){
    // 생략
    
    // 우선순위 큐
    PriorityQueue<Node> pq = new PriorityQueue((x, y) -> x.weight - y.weight);
    pq.add(new Node(1, 0)); // 임의의 노드를 시작점으로 지정
    
    int cnt = 0; // 노드만큼만 반복
    while (!pq.isEmpty()){
    	Node cur = pq.poll();
        cnt++;
        
        // 방문 여부확인
        if (visited[cur.to]){
        	continue;
        }
        visited[cur.to] = true; // 방문 체크
        weightSum += cur.weight; // 전체 가중치 갱신
        
        // 반복 수 확인(마지막 뽑는 노드)
        if (cnt == v) {
        	break;
        }
        
        // 인접한 정점을 작은 가중치 순으로 offer
        for (int i = 0; adjList.get(cur.to).size(); i++){
        	Node adjNode = adjList.get(cur.to).get(i);
            
            if (visited[adjNode.to]) {
            	continue;
            }
            
            pq.offer(adjNode);
        }
        
    }
    
    return weightSum;
}

 

- 전체 코드

static class Node {
    int to;
    int weight;

    public Node(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

public static int prim(int[][] data, int v, int e) {
    int weightSum = 0;

    ArrayList<ArrayList<Node>> adjList = new ArrayList();
    for (int i = 0; i < v + 1; i++) {
        adjList.add(new ArrayList<>());
    }

    for (int i = 0; i < e; i++) {
        // 양방향으로 연결
        adjList.get(data[i][0]).add(new Node(data[i][1], data[i][2]));
        adjList.get(data[i][1]).add(new Node(data[i][0], data[i][2]));
    }

    boolean[] visited = new boolean[v + 1];

    PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> x.weight - y.weight);
    pq.add(new Node(1, 0));

    int cnt = 0;
    while (!pq.isEmpty()) {
        Node cur = pq.poll();
        cnt++;

        if (visited[cur.to]) {
            continue;
        }
        visited[cur.to] = true;
        weightSum += cur.weight;

        if (cnt == v) {
            return weightSum;
        }

        // 인접한 정점을 작은 가중치 순으로 offer
        for (int i = 0; i < adjList.get(cur.to).size(); i++) {
            Node adjNode = adjList.get(cur.to).get(i);

            if (visited[adjNode.to]) {
                continue;
            }

            pq.offer(adjNode);
        }
    }

    return weightSum;
}

 

 

 

[ 참고 및 출처 ]

- 부트캠트 수업 내용 정리

- [Do it! 알고리즘 코딩 테스트 자바 편]