그래프 알고리즘 기초 - 최소신장트리(MST)

By on November 22, 2023

그래프 알고리즘 기초 - 최소 신장 트리(Minimum Spanning Tree)

최소 신장 트리란? (Minimum Spanning Tree)

  • 최소신장 트리는 모든 정점을 포함하면서 가장 적은 비용으로 연결된 부분 그래프를 찾는 알고리즘.
  • 프림 알고리즘과 크루스칼 알고리즘이 있음.
    • 둘의 차이점은 프림 알고리즘은 복잡한 밀집 그래프에 적합하고 크루스칼 알고리즘은 간선이 적은 희소 그래프에 적합하다.

최소 신장 트리(프림 알고리즘)

프림 알고리즘은 한 정점에서 시작하여 현재 선택된 정점의 집합에서 가장 가까운 정점을 선택하고,
해당 정점과 연결된 간선 중에서 최소 가중치 간선을 선택하는 방식으로 동작합니다.

  public class PrimAlgorithm {
    public static void main(String[] args) {
      Map<String, List<Edge>> graph = new HashMap<>();
      graph.put("A", Arrays.asList(new Edge("A", "B", 2), new Edge("A", "D", 5)));
      graph.put("B", Arrays.asList(new Edge("B", "A", 2), new Edge("B", "C", 3)));
      graph.put("C", Arrays.asList(new Edge("C", "B", 3), new Edge("C", "D", 1)));
      graph.put("D", Arrays.asList(new Edge("D", "A", 5), new Edge("D", "C", 1)));
    
      List<Edge> result = prim(graph);
    
      for (Edge edge : result) {
        System.out.println(edge.getFrom() + " - " + edge.getTo() + ": " + edge.getCost());
      }
    }
  
    public static List<Edge> prim(Map<String, List<Edge>> graph) {
      List<Edge> minSpanningTree = new ArrayList<>();
      Set<String> visited = new HashSet<>();
      PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(Edge::getCost));
  
      String startNode = graph.keySet().iterator().next();
      priorityQueue.add(new Edge(startNode, startNode, 0));
  
      while (!priorityQueue.isEmpty()) {
        Edge currentEdge = priorityQueue.poll();
        String currentNode = currentEdge.getTo();
  
        if (!visited.contains(currentNode)) {
          visited.add(currentNode);
          minSpanningTree.add(currentEdge);
  
          for (Edge neighbor : graph.get(currentNode)) {
            if (!visited.contains(neighbor.getTo())) {
              priorityQueue.add(neighbor);
            }
          }
        }
      }
      return minSpanningTree;
    }
  }
  
  class Edge {
    private final String from;
    private final String to;
    private final int cost;
  
    public Edge(String from, String to, int cost) {
      this.from = from;
      this.to = to;
      this.cost = cost;
    }
  
    public String getFrom() {
      return from;
    }
  
    public String getTo() {
      return to;
    }
  
    public int getCost() {
      return cost;
    }
  }

최소 신장 트리(크루스칼 알고리즘)

크루스칼 알고리즘은 모든 간선을 가중치의 오름차순으로 정렬한 뒤, 가중치가 가장 작은 간선부터 차례대로 선택하여 사이클을 형성하지 않는 경우에만 해당 간선을 최소 신장 트리에 추가하는 방식으로 동작합니다.

유니온-파인드 알고리즘을 활용 하여 구성 합니다.

  public class KruskalAlgorithm {

    public static void main(String[] args) {
      Map<String, List<Edge>> graph = new HashMap<>();
      graph.put("A", Arrays.asList(new Edge("A", "B", 2), new Edge("A", "D", 5)));
      graph.put("B", Arrays.asList(new Edge("B", "A", 2), new Edge("B", "C", 3)));
      graph.put("C", Arrays.asList(new Edge("C", "B", 3), new Edge("C", "D", 1)));
      graph.put("D", Arrays.asList(new Edge("D", "A", 5), new Edge("D", "C", 1)));
  
      List<Edge> result = kruskal(graph);
  
      for (Edge edge : result) {
        System.out.println(edge.getFrom() + " - " + edge.getTo() + ": " + edge.getCost());
      }
    }
  
    public static List<Edge> kruskal(Map<String, List<Edge>> graph) {
      List<Edge> minSpanningTree = new ArrayList<>();
      List<Edge> edges = new ArrayList<>();
  
      for (List<Edge> edgeList : graph.values()) {
        edges.addAll(edgeList);
      }
  
      edges.sort(Comparator.comparingInt(Edge::getCost));
  
      Map<String, String> parent = new HashMap<>();
      Map<String, Integer> rank = new HashMap<>();
  
      for (String node : graph.keySet()) {
        parent.put(node, node);
        rank.put(node, 0);
      }
  
      for (Edge edge : edges) {
        String root1 = find(parent, edge.getFrom());
        String root2 = find(parent, edge.getTo());
  
        if (!root1.equals(root2)) {
          minSpanningTree.add(edge);
          union(parent, rank, root1, root2);
        }
      }
  
      return minSpanningTree;
    }
  
    private static String find(Map<String, String> parent, String node) {
      if (parent.get(node).equals(node)) {
        return node;
      }
      return find(parent, parent.get(node));
    }
  
    private static void union(Map<String, String> parent, Map<String, Integer> rank, String node1, String node2) {
      String root1 = find(parent, node1);
      String root2 = find(parent, node2);
  
      if (!root1.equals(root2)) {
        if (rank.get(root1) < rank.get(root2)) {
          parent.put(root1, root2);
        } else if (rank.get(root1) > rank.get(root2)) {
          parent.put(root2, root1);
        } else {
          parent.put(root1, root2);
          rank.put(root2, rank.get(root2) + 1);
        }
      }
    }
  }
  
  class Edge {
    private final String from;
    private final String to;
    private final int cost;
  
    public Edge(String from, String to, int cost) {
      this.from = from;
      this.to = to;
      this.cost = cost;
    }
  
    public String getFrom() {
      return from;
    }
  
    public String getTo() {
      return to;
    }
  
    public int getCost() {
      return cost;
    }
  }

Back to blog