[Algorithm] 최소신장트리(MST)

신장트리

n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선들로 이루어진 트리

최소신장트리(MST, Minimum Spanning Tree)

무향 가중치 그래프에서 신장트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

Prim Algorithm

Kruskal Algorithm

Reference

『IT CookBook, 자바로 배우는 쉬운 자료구조』, 이지영 집필, 한빛아카데미(2008)

『 SW 문제해결 응용 - 구현 - 그래프의 최소 비용 문제』

[Algorithm] 최소신장트리(MST) - Kruskal

간선을 하나씩 선택해서 MST를 찾는 알고리즘

1. 최소, 모든 간선을 가중치에 따라 오름차순으로 정렬
2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴
   • 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택
3. n-1개의 간선이 선택될 때 까지 2를 반복

code

Edge

public class Edge {
    int adjvertex; // 간선의 다른쪽 끝 정점
    int weight;    // 간선의 가중치
    public Edge(int v, int wt) {
        adjvertex = v;
        weight    = wt;
    }
}

KruskalMST

import java.util.*;
public class KruskalMST {
    int N, M; // 그래프 정점, 간선의 수
    List<Edge>[] graph;
    UnionFind uf; // Union-Find 연산을 사용하기 위해    
    Edge[] tree;    
    static class Weight_Comparison implements Comparator<Edge> { //weight를 기준으로 우선순위큐를  사용하기 위해
        public int compare(Edge e, Edge f) {
            if(e.weight > f.weight)
                return 1;
            else if(e.weight < f.weight)
                return -1;        
            return 0;
        }        
    }
    public KruskalMST(List<Edge>[] adjList, int numOfEdges) {
        N = adjList.length;
        M = numOfEdges;
        graph = adjList;
        uf = new UnionFind(N);    // Union-Find 연산을 사용하기 위해    
        tree = new Edge[N-1];
    }
    public Edge[] mst()    {  // Kruskal 알고리즘        
        Weight_Comparison BY_WEIGHT = new Weight_Comparison();  // 우선순위큐를  weight 기준으로 구성하기 위해        
        PriorityQueue<Edge> pq = new PriorityQueue<Edge>(M, BY_WEIGHT);  // 자바 라이브러리의 우선순위큐 사용
                                    // 우선순위큐의 크기로 M(간선의 수)을 지정, BY_WEIGHT는 line 24의 comparator
        for (int i = 0; i < N; i++){ 
            for (Edge e : graph[i]){
                pq.add(e);  // edgeArray의 간선 객체들을 pq에 삽입
            }
        }        
        int count = 0;    
        while (!pq.isEmpty() && count < N-1) {
            Edge e = pq.poll();          // 최소 가중치를 가진 간선를 pq에서 제거하고 가져옴
            int u = e.vertex;            // 가져온 간선의 한 쪽 정점
            int v = e.adjvertex;          // 가져온 간선의 다른 한 쪽 정점
            if (!uf.isConnected(u, v)) { // v와 w가 각각 다른 집합에 속해 있으면
                uf.union(u, v);          // v가 속한 집합과 u가 속한 집합의 합집합 수행
                tree[count++] = e;       // e를 MST의 간선으로서 tree에 추가
            }
        }            
        return tree;
    }
}

UnionFind

public class UnionFind {  
    protected  int[] p;    // 배열크기는 정점의 수 N이고 p[i]는 i의 부모 원소를 저장한다. 
    protected  int[] rank; 

    public UnionFind(int N) {
        p = new int[N];
        rank = new int[N];
        for (int i = 0; i < N; i++) {
            p[i]    = i;  // 초기엔 N개의 트리가 각각 i 자기 자신이 부모이기 떄문에 
            rank[i] = 0;  // 초기엔 N개의 트리 각각의 rank를 0으로 초기화 
        }
    }
    //i가 속한 집합의 루트노드를 재귀적으로 찾고 최종적으로 경로상의 각 원소의 부모를 루트노드로 만든다.
    protected int find(int i) { // 경로 압축
        if ( i != p[i])   
            p[i] = find(p[i]);  //리턴하며 경로상의 각 노드의 부모가 루트가되도록 만든다.
        return p[i];
    }
    //i와 j가 같은 트리에 있는지를 검사
    public boolean isConnected(int i, int j) {
        return find(i) == find(j); 
    }
    public void union(int i, int j) {  // Union 연산
        int iroot = find(i);
        int jroot = find(j);
        if (iroot == jroot) return;  // 루트노드가 동일하면 더이상의 수행없이 그대로 리턴
        // rank가 높은 루트노드가 승자로 union을 수행한다.
        if (rank[iroot] > rank[jroot]) 
            p[jroot] = iroot;               // iroot가 승자
        else if (rank[iroot] < rank[jroot]) 
            p[iroot] = jroot;               // jroot가 승자
        else {
            p[jroot] = iroot;  // 둘중에 하나 임의로 승자
            rank[iroot]++;     // iroot의 rank 1 증가
        }
    }
}

수행시간

간선을 정렬(또는 우선순위큐의 삽입과 삭제)하는데 소요되는 시간 $O(MlogM) = O(MlogN)$

신장트리가 만들어질 때까지 간선에 대해 isConnected()와 union()을 수행하는 시간 $O((M+N)logN)$
$$
O(MlogN) + O((M+N)logN) = O(MlogN)
$$

Reference

『IT CookBook, 자바로 배우는 쉬운 자료구조』, 이지영 집필, 한빛아카데미(2008)

『SW 문제해결 응용 - 구현 - 그래프의 최소 비용 문제』
https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AV3GBeD6AF4BBARB#

[Algorithm] 최소신장트리(MST) - Prim

하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어가는 방식

1. 임의의 정점을 하나 선택
2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
3. 모든 정점이 선택될 때까지 1, 2 과정을 반복

code

Edge

public class Edge {
    int adjvertex; // 간선의 다른쪽 끝 정점
    int weight;    // 간선의 가중치
    public Edge(int v, int wt) {
        adjvertex = v;
        weight    = wt;
    }
}

PrimMST

import java.util.List;
public class PrimMST {
    int N; // 그래프 정점의 수
    List<Edge>[] graph;

    public PrimMST(List<Edge>[] adjList) { // 생성자
        N = adjList.length;
        graph = adjList;
    }

    public int[] mst (int s) { // Prim 알고리즘,s는 시작정점
        boolean[] visited = new boolean[N]; // 방문된 정점은 true로
        int[] D = new int[N];
        int[] previous = new int[N]; // 최소신장트리의 간선으로 확정될 때 간선의 다른 쪽 (트리의)끝점
        for(int i = 0; i < N; i++){  // 초기화
            visited[i] = false;
            previous[i] = -1;
            D[i] = Integer.MAX_VALUE;  // D[i]를 최댓값으로 초기화
        }
        previous[s] = 0;  //시작정점 s의 관련 정보 초기화
        D[s] = 0;

        for(int k = 0; k < N; k++){ // 방문안된 정점들의 D 원소들중 에서 최솟값가진 정점 minVertex 찾기            
            int minVertex = -1;
            int min = Integer.MAX_VALUE;
            for(int j=0;j<N;j++){
                if ((!visited[j])&&(D[j] < min)){
                    min = D[j];
                    minVertex = j;
                }
            }
            visited[minVertex] = true;
            for (Edge i : graph[minVertex]){ // minVertex에 인접한 각 정점의 D의 원소 갱신             
                if (!visited[i.adjvertex]){  // 트리에 아직 포함 안된 정점이면
                    int currentDist = D[i.adjvertex];
                    int newDist = i.weight;
                    if (newDist < currentDist){             
                        D[i.adjvertex] = newDist; // minVertex와 연결된 정점들의 D 원소 갱신
                        previous[i.adjvertex] = minVertex; // 트리 간선 추출을 위해 
                    }
                }
            }
        }   
        return previous; // 최소신장트리 간선 정보 리턴
    }
}

수행시간

Prim 알고리즘은 N번의 반복을 통해 minVertex를 찾고 minVertex에 인접하면서 트리에 속하지 않은 정점에 해당하는 D 의 원소 값을 갱신

PrimMST 클래스에서는 minVertex를 배열 D에서 탐색하는 과정에서 $O(N)$ 시간이 소요되고, minVertex에 인접한 정점들을 검사하여 D의 해당 원소를 갱신하므로 $O(N)$ 시간이 소요된다. 따라서 총 수행시간은
$$
N\times(O(N) +O(N)) = O(N^2)
$$

Reference

『IT CookBook, 자바로 배우는 쉬운 자료구조』, 이지영 집필, 한빛아카데미(2008)

『SW 문제해결 응용 - 구현 - 그래프의 최소 비용 문제』

​ https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AV3GBeD6AF4BBARB#

PowerSet (부분집합)

부분집합을 구하는 3가지 방법

1. 조합을 이용한 방법

n개중 r개를 선택하는 조합알고리즘을 이용하여

for문으로 r을 0부터 n까지 선택한 결과.

2. 재귀함수를 이용하는 방법

1. 현재 인덱스를 포함하는 경우
2. 현재 인덱스를 포함하지 않는 경우

위 2가지 경우를 재귀호출하여 인덱스가 모든 배열을 순회했을때 결과.

3. 비트연산을 이용하는 방법

집합의 개수가 4개라면 0000~1111을 순회하며 해당 비트가 1인지를 확인하는 방법

code

public class Main {
    static boolean[] visit;

    public static void main(String[] args) {
        int N = 4;
        visit = new boolean[N];

        for (int i = 0; i <= N; i++) {
            combination(N, i, 0, 0); //N개중 i개를 뽑은 모든경우
        }
        System.out.println("----------------------");

        powerSet(visit.length, 0);
        System.out.println("----------------------");

        bit(N);

    }
    //조합
    private static void combination(int n, int r, int depth, int start) {
        if (depth == r) {
            // print
            for (int i = 0; i < visit.length; i++) {
                if (visit[i])
                    System.out.print(i + " ");
            }
            System.out.println();
            return;
        }
        for (int i = start; i < n; i++) {
            if (visit[i] == false) {
                visit[i] = true;
                combination(n, r, depth + 1, i);
                visit[i] = false;
            }
        }
    }

    // 재귀호출을 이용한 방법
    static void powerSet(int n, int idx) {
        if (idx == n) {
            // print
            for (int i = 0; i < visit.length; i++) {
                if (visit[i])
                    System.out.print(i + " ");
            }
            System.out.println();
            return;
        }

        // 현재 인덱스를 포함하는 경우
        visit[idx] = true;
        powerSet(n, idx + 1);

        // 현재 인덱스를 포함하지 않는 경우
        visit[idx] = false;
        powerSet(n, idx + 1);
    }

    // Bit연산을 이용하는 방법
    static void bit(int n) {
        for (int i = 0; i < 1 << n; i++) {// n이 4일때, 0000~1111
            for (int j = 0; j < n; j++) { // 0001, 0010, 0100, 1000
                // 각 자리 논리합(AND)의 결과가 0이 아닐경우
                // (해당bit를 포함함을 의미)
                if ((i & 1 << j) != 0)
                    System.out.print(j + " ");
            }
            System.out.println();
        }
    }

}

Disjoint-Set (서로소 집합)

서로 중복되지 않는 부분 집합들 로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조

• 즉, 공통 원소가 없는 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조이다.

Union-Find

Disjoint Set을 표현할 때 사용하는 알고리즘

Union-Find의 연산

• make-set(x)

  • 초기화
  • x를 유일한 원소로 하는 새로운 집합을 만든다.

  private static void makeSet(int n){
      parent = new int[n];
      for(int i = 1; i <= n; i++){
      parent[i] = i;
  }

• union(x, y)

  • 합하기
  • x가 속한 집합과 y가 속한 집합을 합친다. 즉, x와 y가 속한 두 집합을 합치는 연산

  private static void union(int x, int y) {
      x = find(x);
      y = find(y);
      if (x != y) {
          if (x < y)
              parent[y] = x;
          else
              parent[x] = y;
      }
  }

• find(x)

  • 찾기
  • x가 속한 집합의 대표값(루트 노드 값)을 반환한다. 즉, x가 어떤 집합에 속해 있는지 찾는 연산

  private static int find(int x) {
      if (x == parent[x])
          return x;
      else
          return parent[x] = find(parent[x]);
  }

CaseOfNumber - 조합 & 중복조합 &순열 & 중복순열

조합(Combination)

서로 다른 물건들 중 몇 가지 대상을 뽑는 것을 조합이라고 한다.

서로 다른 n 개의 원소 중 r 개를 선택 (순서 X, 중복 X)

중복 조합(Homogeneous)

서로 다른 종류의 대상들 중에서 중복을 허락하여 몇 개를 택하는 조합을 중복조합이라고 한다.

서로 다른 n 개의 원소 중 r 개를 선택 (순서 X, 중복 O)

순열(Permutation)

서로 다른 물건들 중 몇 가지 대상을 뽑아 일렬로 나열하는 것을 순열이라고 한다.

서로 다른 n개의 원소 중 r개를 선택 (순서O , 중복 O)

중복 순열(Product)

서로 다른 물건들 중에서 중복을 허용하여 몇 개를 택하는 순열을 중복순열이라고 한다.

서로 다른 n개의 원소 중 r개를 선택 (순서O , 중복 O)

code

import java.util.Arrays;

public class MyCombi {
    static int[] data = { 1,2,3,4 };
    static int[] res;
    static boolean[] visit;
    static int cnt;

    public static void main(String[] args) {
        int N = 4, R = 2;
        res = new int[R];
        visit = new boolean[N];

        cnt = 0;
        solve1(N, R, 0);
        System.out.println(cnt);

        cnt = 0;
        solve2(N, R, 0);
        System.out.println(cnt);

        cnt = 0;
        solve3(N, R, 0, 0);
        System.out.println(cnt);

        cnt = 0;
        solve4(N, R, 0, 0);
        System.out.println(cnt);
    }

    //중복순열: 순서가 중요하고(123!=321), 중복을 허용하는 경우
    private static void solve1(int n, int r, int depth) {
        if (depth == r) {
            System.out.println(Arrays.toString(res));
            cnt++;
            return;
        }

        for (int i = 0; i < n; i++) {
            res[depth] = data[i];
            solve1(n, r, depth + 1);
        }
    }

    //순열: 순서가 중요하고(123!=321), 중복을 허용하지 않는 경우
    private static void solve2(int n, int r, int depth) {
        if (depth == r) {
            System.out.println(Arrays.toString(res));
            cnt++;
            return;
        }

        for (int i = 0; i < n; i++) {
            if (visit[i] == false) {
                visit[i] = true;
                res[depth] = data[i];
                solve2(n, r, depth + 1);
                visit[i] = false;
            }
        }
    }

    //중복조합: 순서가 중요하지 않고(123==321), 중복을 허용하는 경우
    private static void solve3(int n, int r, int depth, int start) {
        if (depth == r) {
            System.out.println(Arrays.toString(res));
            cnt++;
            return;
        }

        for (int i = start; i < n; i++) {
            res[depth] = data[i];
            solve3(n, r, depth + 1, i);
        }
    }

    //조합: 순서가 중요하지 않고(123==321), 중복을 허용하지 않는 경우
    private static void solve4(int n, int r, int depth, int start) {
        if (depth == r) {
            System.out.println(Arrays.toString(res));
            cnt++;
            return;
        }

        for (int i = start; i < n; i++) {
            if (visit[i] == false) {
                visit[i] = true;
                res[depth] = data[i];
                solve4(n, r, depth + 1, i);
                visit[i] = false;
            }
        }
    }

}