CS/알고리즘

알고리즘 - MST

빈둥벤둥 2021. 2. 15. 22:21

MST

MST

  • Minimum Spanning Trees. 최소 신장 트리.

  • 조건: 싸이클이 없는 무향 연결 그래프. 연결 그래프란 모든 정점 간에 경로가 존재하는 그래프를 말한다. 

  • 간선의 합이 최소인 신장트리를 말한다.

 

Prim Algorithmn

    • 임의의 시작 노드를 골라 min heap에 insert한 후 노드와 연결된 노드를 min heap에 insert해준다. 거리가 작은 노드부터 꺼내며 꺼낼 때마다 연결된 노드를 찾아 min heap에 넣어주는 과정을 반복한다. 

    • min heap에 저장되는 정보는 현재 노드 정보와 이전 노드에서 현재 노드까지의 거리 정보이다.
    • 수행시간: O(ElogV)
    • 구현 with JAVA (백준 1197 최소 스패닝 트리)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void prim() {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.offer(new Node(1, 0)); //1번 노드부터 시작.
        
        while(!q.isEmpty()) {
            Node current = q.poll(); //큐에서 cost가 가장 작은 노드를 꺼낸다.
            
            if(visited[current.node] == false) visited[current.node] = true;
            else continue; //이미 방문한 노드는 무시한다.     
            
            min += current.cost;
            for(int i = 0; i < list[current.node].size(); i++) {
                Node next = list[current.node].get(i);
                if(visited[next.node] == false) q.offer(next);
            }
        }
    }
 cs

 

Kruskal Algorithmn

    • 모든 연결 노드의 정보와 거리 정보를 min heap에 저장한 후 순서대로 싸이클을 형성하지 않는 노드를 선택한다.

    • min heap에 저장되는 정보는 연결되어 있는 두 노드와 그 노드의 거리 정보이다. 

    • union-find를 사용해 싸이클을 검사한다.
      • find(합집합 찾기): 현재 노드가 속한 집합의 부모 노드를 찾는다.
      • union(합집합): 두 집합을 합친다. 즉 두 집합의 부모를 같은 부모로 설정한다.

    • 수행시간: O(ElogV)

    • 구현 with JAVA (백준 1197 최소 스패닝 트리)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
    public static void kruskal() {
        for(int i = 1; i < v + 1; i++) {
            parent[i] = i; //부모를 나 자신으로 초기화.
        }
        
        //pq는 간선에 대한 정보를 모두 담고있으며 cost순으로 오름차순 되어있는 우선순위큐.
        while(!pq.isEmpty()) {
            Node2 node = pq.poll();
            
            //s와 e의 각각의 부모를 찾는다
            int p1 = find(node.s);
            int p2 = find(node.e);
            
            if(p1 != p2) { //서로의 부모가 다르다면 싸이클이 없으므로 연결해 준다.
                union(p1, p2);
                min += node.cost;
            }
        }
    }
    
    public static int find(int a) {
        if(parent[a] == a) return a;
        else return parent[a] = find(parent[a]);
    }
    
    public static void union(int a, int b) {
        parent[a] = b;
    }
 cs

 

 

reference