[Algorithm] 최소신장트리

무향 그래프에서 신장트리는 노드를 그대로 두고, 간선을 (노드의 개수 - 1)개만 남겨 트리가 되도록 만드는 것이다.

간선들이 가중치를 갖는 그래프에서 간선 가중치의 합이 가장 작은 트리를 최소신장트리라고 한다.

 

프림 알고리즘

프림 알고리즘은 집합 S를 공집합에서 시작해 모든 노드가 포함될 때까지 키워나간다.

노드가 하나 포함될 때마다 간선이 하나씩 확정된다.

 

확정 노드를 저장할 S와 시작 노드부터 각 노드에 도착할 때 필요한 가중치를 저장한 d를 준비한다.

d는 아주 큰 수로 초기화한다. 그리고 시작 노드는 0으로 초기화한다.

초기 상태

그리고 집합 S에 모든 노드가 포함되기까지 노드를 추가한다.

추가할 때, 먼저 현재 노드 위치에 연결된 노드에 가중치를 계산한다.

가중치 계산

 그에 대한 최소를 찾아 S에 포함시키고, S에 포함된 노드와 연결된 노드의 가중치를 갱신하는 방식으로 반복한다.

최소를 찾아 S에 포함시키고, 연결된 노드 최소 가중치 갱신

위와 같이 갱신되는데, 본래 9의 가중치를 가졌던 노드 값이 7로 변경된 것은, 최소를 찾아 갱신되었기 때문이다.

계속 반복해 진행하면,

노드 추가되는 것 반복

다음과 같은 결과를 얻을 수 있다.

완성된 최소 신장 트리

크루스칼 알고리즘

크루스칼 알고리즘은 싸이클을 만들지 않는 범위에서 최소 비용 간선을 하나씩 더해가면서 최소신장트리를 만든다.

프림 알고리즘이 간선을 하나씩 늘려가면서 최소신장트리를 완성하지만, 크루스칼 알고리즘은 전체 노드를 각각의 트리로 생각하고, 트리를 줄여가면서 하나의 최소신장트리로 만드는 것으로 생각하면 된다.

 

최소 비용의 간선을 제거하면서 트리를 하나씩 만든다.

가장 최소비용 간선 제거하면서 트리 생성

그 다음 최소비용을 찾아 트리를 생성한다.

새로운 트리 생성

간선이 삭제되면서 트리 확장

이미 여러 노드로 구성된 트리 2개가 합쳐져야 할 경우 하나로 합친다.

2개 트리 하나로 합쳐짐

최소 비용의 간선을 추가하려고 할 때, 싸이클이 형성된다면 그 다음 최소를 찾아 간선을 제거해 트리를 구성한다.

싸이클로 인해 그 다음 최소 비용 간선을 제거

간선의 수가 (노드의 개수 - 1)가 완료되면 종료된다.

크루스칼 알고리즘으로 완성된 최소신장트리

 

프림 알고리즘의 경우 노드에 저장되는 가중치가 이전 노드의 가중치와의 합으로 저장되면 해당 노드에 도달하는데 걸리는 최소 거리가 된다. 나중에 최단거리를 구하는 알고리즘에서 사용될 수 있다.

 

크루스칼 알고리즘 소스코드

import java.util.*;

class Edge implements Comparable<Edge> { // 간선 정보
  private int distance;
  private int nodeA;
  private int nodeB;

  public Edge (int distance, int nodeA, int nodeB) {
    this.distance = distance;
    this.nodeA = nodeA;
    this.nodeB = nodeB;
  }

  public int getDistance() {
    return this.distance;
  }

  public int getNodeA() {
    return this.nodeA;
  }

  public int getNodeB() {
    return this.nodeB;
  }

  public int compareTo(Edge other) { // 간선 비용이 적은 것부터 정렬할 수 있도록
    if (this.distance < other.getDistance()) {
      return -1;
    }
    return 1;
  }
}

class Main {

  public static int n, m;
  public static int[] parentNode = new int[30001];
  public static List<Edge> list = new ArrayList<>();

  // 최소신장트리이기 때문에 싸이클이 발생하지 않도록 확인하기 위해
  public static int findParent(int x) { 
    if (x == parentNode[x]) return x;
    return parentNode[x] = findParent(parentNode[x]);
  }

  public static void unionParent(int a, int b) {
    a = parentNode[a];
    b = parentNode[b];
    if (a < b) {
      parentNode[b] = a;
    } else {
      parentNode[a] = b;
    }
  }

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    m = sc.nextInt();
    
    for(int i = 0; i <= n; i++) {
      parentNode[i] = i;
    }

    for(int i = 0; i < m; i++) {
      int a = sc.nextInt();
      int b = sc.nextInt();
      int d = sc.nextInt();
      list.add(new Edge(d, a, b));
    }
    sc.close();

    // 간선 정보 정렬
    Collections.sort(list);
    
    int result = 0;
    for (int i = 0; i < list.size(); i++) {
      int d = list.get(i).getDistance();
      int a = list.get(i).getNodeA();
      int b = list.get(i).getNodeB();
      // 간선을 잇는 노드가 이미 같은 집합 내에 있다면 사이클 발생
      if (findParent(a) != findParent(b)) {
        unionParent(a, b);
        result += d;
      }
    }

    
    System.out.println(result);



  } // end main
}

위상 정렬 소스코드

import java.util.*;

class Main {

  public static int v, e;
  // 진입차수 정보
  public static int[] indegree = new int[30001];
  // 그래프 2차원 리스트 (인접리스트)
  public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
  // 출력 결과 저장
  public static List<Integer> result = new ArrayList<>();

  public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
    v = sc.nextInt();
    e = sc.nextInt();

    for (int i = 0; i <= v; i++) {
      graph.add(new ArrayList<Integer>());
    }
    
    for (int i = 0; i < e; i++) {
      int a = sc.nextInt();
      int b = sc.nextInt();
      indegree[b]++; // 진입차수++
      graph.get(a).add(b);
    }

    // 진입 차수 0인 노드 추가할 큐
    Queue<Integer> q = new LinkedList<>();
    for (int i = 1; i <= v; i++) {
      if (indegree[i] == 0) {
        q.offer(i);
      }
    }

    while(!q.isEmpty()) {
      int now = q.poll();
      result.add(now);
      for(int i : graph.get(now)) {
        if (--indegree[i] == 0) q.offer(i);
      }
    }
    
    for (int r : result) {
      System.out.print(r + " ");
    }
    System.out.println();
    

  } // end main
}