최소 신장 트리에 대한 이해

 최소 신장 트리는 가중치가 부여된 무방향 그래프에서 모든 정점을 연결하되, 전체 간선 가중치 합이 최소가 되는 트리를 찾는 알고리즘이다.

 이 개념은 통신망 구축, 도로 건설, 전력망 설계 처럼, 각 지점을 연결하는 비용이나 자원을 최소화하는 문제에 활용된다.

 문제의 특성에 따라, 크루스칼(Kruskal), 프림(Prim), 보루프카(Borůvka) 등의 알고리즘 등으로 효율적으로 최적화할 수 있다.

 크루스칼 알고리즘은 모든 간선을 비용 순으로 정렬한 뒤, 가장 작은 비용의 간선부터 하나씩 연결해 나가면서 사이클이 생기지 않을때만 트리에 추가하는 방식이다. 이때 사이클 검사는 유니온 파인드 자료구조를 통해 처리되며, 전체 시간 복잡도는 간선의 정렬에 걸리는 O(E * log E)로 측정된다. 즉, 간선 수가 많지 않은(희소한) 그래프에서 적절하며, 구현기 직관적이고 간결하다는 장점이 있다.

• 코드

  import java.util.*;
  
  class Edge implements Comparable<Edge> {
      int src, dest, weight;
      
      public Edge(int src, int dest, int weight) {
          this.src = src;
          this.dest = dest;
          this.weight = weight;
      }
      
      public int compareTo(Edge other) {
          return this.weight - other.weight;
      }
  }
  
  class Graph {
      int V, E;
      Edge[] edges;
      
      public Graph(int V, int E) {
          this.V = V;
          this.E = E;
          edges = new Edge[E];
      }
  }
  
  class DisjointSet {
      int[] parent;
      int[] rank;
      
      public DisjointSet(int n) {
          parent = new int[n];
          rank = new int[n];
          for (int i = 0; i < n; i++) {
              parent[i] = i;
              rank[i] = 0;
          }
      }
      
      public int find(int x) {
          if (parent[x] != x)
              parent[x] = find(parent[x]);
          return parent[x];
      }
      
      // union 메서드: rank 비교를 별도의 compareRank 함수를 사용
      public void union(int x, int y) {
          int xroot = find(x);
          int yroot = find(y);
          if (xroot == yroot) return;
          
          if (compareRank(xroot, yroot) < 0) {
              parent[xroot] = yroot;
          } else if (compareRank(xroot, yroot) > 0) {
              parent[yroot] = xroot;
          } else {
              parent[yroot] = xroot;
              rank[xroot]++;
          }
      }
      
      // 두 집합의 rank를 비교하는 별도의 함수
      public int compareRank(int x, int y) {
          return Integer.compare(rank[x], rank[y]);
      }
  }
  
  public class KruskalMST {
      
      public static List<Edge> kruskalMST(Graph graph) {
          List<Edge> result = new ArrayList<>();
          // 모든 간선을 가중치 순으로 정렬
          Arrays.sort(graph.edges);
          
          DisjointSet ds = new DisjointSet(graph.V);
          
          // 간선 하나씩 선택하며 사이클이 형성되지 않을 경우 MST에 추가
          for (Edge edge : graph.edges) {
              int x = ds.find(edge.src);
              int y = ds.find(edge.dest);
              
              if (x != y) {
                  result.add(edge);
                  ds.union(x, y);
              }
          }
          return result;
      }
      
      public static void main(String[] args) {
          int V = 4, E = 5;
          Graph graph = new Graph(V, E);
          
          // 간선 추가 (예제: 0-1:10, 0-2:6, 0-3:5, 1-3:15, 2-3:4)
          graph.edges[0] = new Edge(0, 1, 10);
          graph.edges[1] = new Edge(0, 2, 6);
          graph.edges[2] = new Edge(0, 3, 5);
          graph.edges[3] = new Edge(1, 3, 15);
          graph.edges[4] = new Edge(2, 3, 4);
          
          List<Edge> mst = kruskalMST(graph);
          System.out.println("Kruskal MST:");
          for (Edge e : mst) {
              System.out.println(e.src + " -- " + e.dest + " == " + e.weight);
          }
      }
  }
  

 프림 알고리즘은 한 정점에서 출발해 현재 트리에 연결된 정점과 인접한 간선 중 비용이 가장 작은 것을 선택해 확장하는 방식이다. 노드별 우선순위 큐를 사용해 다음 선택 간선을 관리하며, 시간 복잡도는 인접 리스트 기반으로 구현하면 O(E + Vlog V)가 된다. 노드별 간선의 우선도를 기반으로 하기 때문에 간선의 밀도가 높은 그래프에서 더 효율적이다. 알고리즘 특성상 정점을 특정하기 때문에 한 지점에서 최소 연결망을 찾을 때 유리하다.

• 코드

  import java.util.*;
  
  class Pair implements Comparable<Pair> {
      int vertex, key;
      
      public Pair(int vertex, int key) {
          this.vertex = vertex;
          this.key = key;
      }
      
      public int compareTo(Pair other) {
          return this.key - other.key;
      }
  }
  
  public class PrimMST {
      
      public static void primMST(List<List<Pair>> adj, int V) {
          boolean[] inMST = new boolean[V];
          int[] key = new int[V];
          int[] parent = new int[V];
          Arrays.fill(key, Integer.MAX_VALUE);
          
          PriorityQueue<Pair> pq = new PriorityQueue<>();
          key[0] = 0;
          parent[0] = -1;
          pq.add(new Pair(0, key[0]));
          
          while (!pq.isEmpty()) {
              int u = pq.poll().vertex;
              inMST[u] = true;
              
              for (Pair neighbor : adj.get(u)) {
                  int v = neighbor.vertex;
                  int weight = neighbor.key;
                  if (!inMST[v] && weight < key[v]) {
                      key[v] = weight;
                      parent[v] = u;
                      pq.add(new Pair(v, key[v]));
                  }
              }
          }
          
          System.out.println("Prim MST:");
          for (int i = 1; i < V; i++) {
              System.out.println(parent[i] + " - " + i + " : " + key[i]);
          }
      }
      
      // 무방향 그래프의 간선 추가: 양쪽에 추가
      public static void addEdge(List<List<Pair>> adj, int u, int v, int w) {
          adj.get(u).add(new Pair(v, w));
          adj.get(v).add(new Pair(u, w));
      }
      
      public static void main(String[] args) {
          int V = 5;
          List<List<Pair>> adj = new ArrayList<>();
          for (int i = 0; i < V; i++) {
              adj.add(new ArrayList<>());
          }
          
          // 예제 그래프 간선 추가
          addEdge(adj, 0, 1, 2);
          addEdge(adj, 0, 3, 6);
          addEdge(adj, 1, 2, 3);
          addEdge(adj, 1, 3, 8);
          addEdge(adj, 1, 4, 5);
          addEdge(adj, 2, 4, 7);
          addEdge(adj, 3, 4, 9);
          
          primMST(adj, V);
      }
  }
  

 보루프카 알고리즘은 각 노드(컴포넌트)가 자신과 연결된 가장 낮은 비용 간선을 동시에 선택해 병합하는 과정을 반복한다. 크루스칼과 프림의 방식이 섞여있다고 생각할 수 있다. 각 노드가 동시에 선택하기 때문에, 병렬 처리가 가능하다. 전체 복잡도는 O(E log V)이다. 대규모 분산 시스템이나 외부 메모리 환경에서 활용 가치가 높다. 솔린(Sollin)이라는 사람이 보루프카 이후에 알고리즘을 다시 소개하면서 솔린 알고리즘이라고도 불린다.

• 코드

  import java.util.*;
  
  class BoruvkaEdge {
      int src, dst, weight;
  
      public BoruvkaEdge(int _src, int _dst, int _weight) {
          src = _src;
          dst = _dst;
          weight = _weight;
      }
  }
  
  public class BoruvkaMST {
      static class Subset {
          int parent, rank;
  
          public Subset(int _parent, int _rank) {
              parent = _parent;
              rank = _rank;
          }
      }
  
      public static int boruvkaMST(List<BoruvkaEdge> edges, int V) {
          // 각 정점을 독립적인 컴포넌트로 취급
          Subset[] subsets = new Subset[V];
          for (int i = 0; i < V; i++) {
              subsets[i] = new Subset(i, 0);
          }
  
          int numTrees = V;
          int MSTweight = 0;
          // 각 컴포넌트에서 선택된 최소 간선을 저장할 배열
          BoruvkaEdge[] cheapest = new BoruvkaEdge[V];
  
          while (numTrees > 1) {
              Arrays.fill(cheapest, null);
  
              // 모든 간선을 순회하며 각 컴포넌트별 최소 간선을 갱신
              for (BoruvkaEdge edge : edges) {
                  // 각 컴포넌트의 부모를 찾
                  int set1 = find(subsets, edge.src);
                  int set2 = find(subsets, edge.dst);
  
                  if (set1 == set2)
                      continue;
  
                  if (cheapest[set1] == null || cheapest[set1].weight > edge.weight) {
                      cheapest[set1] = edge;
                  }
                  if (cheapest[set2] == null || cheapest[set2].weight > edge.weight) {
                      cheapest[set2] = edge;
                  }
              }
  
              // 각 컴포넌트의 최소 간선을 MST에 추가
              for (int i = 0; i < V; i++) {
                  if (cheapest[i] != null) {
                      BoruvkaEdge edge = cheapest[i];
                      int set1 = find(subsets, edge.src);
                      int set2 = find(subsets, edge.dst);
  
                      if (set1 == set2)
                          continue;
  
                      MSTweight += edge.weight;
                      union(subsets, set1, set2);
                      System.out.println("Edge " + edge.src + " - " + edge.dst + " added with weight " + edge.weight);
                      numTrees--;
                  }
              }
          }
          System.out.println("Boruvka MST Weight: " + MSTweight);
          return MSTweight;
      }
  
      // 컴포넌트의 부모 찾기 + 경로 압축
      public static int find(Subset[] subsets, int i) {
          if (subsets[i].parent != i) {
              subsets[i].parent = find(subsets, subsets[i].parent);
          }
          return subsets[i].parent;
      }
  
      private static int compareRank(Subset[] subsets, int xRoot, int yRoot) {
          return Integer.compare(subsets[xRoot].rank, subsets[yRoot].rank);
      }
  
      public static void union(Subset[] subsets, int x, int y) {
          int xRoot = find(subsets, x);
          int yRoot = find(subsets, y);
          if (xRoot == yRoot)
              return;
  
          int cmp = compareRank(subsets, xRoot, yRoot);
          if (cmp < 0) {
              subsets[xRoot].parent = yRoot;
          } else if (cmp > 0) {
              subsets[yRoot].parent = xRoot;
          } else {
              subsets[yRoot].parent = xRoot;
              subsets[xRoot].rank++;
          }
      }
  
      public static void main(String[] args) {
          int V = 4;
          List<BoruvkaEdge> edges = new ArrayList<>();
          // 예제 간선 추가 (예: 0-1:10, 0-2:6, 0-3:5, 1-3:15, 2-3:4)
          edges.add(new BoruvkaEdge(0, 1, 10));
          edges.add(new BoruvkaEdge(0, 2, 6));
          edges.add(new BoruvkaEdge(0, 3, 5));
          edges.add(new BoruvkaEdge(1, 3, 15));
          edges.add(new BoruvkaEdge(2, 3, 4));
  
          boruvkaMST(edges, V);
      }
  }
  

 각 알고리즘은 탐색 기준, 자료 구조, 복잡도, 그래프 밀도 등에 따라 아래와 같이 정리할 수 있다.

기준	크루스칼	프림	보루프카
탐색 단위	간선 중심 (전역 정렬)	정점 중심 (현재 트리에서 확장)	컴포넌트 중심 (각자의 최소 간선 선택)
자료구조	Union-Find, 정렬 배열	우선순위 큐(PQ), 인접 리스트	Union-Find, 최소 간선 배열
복잡도 (Adj. List)	O(E log E) ≈ O(E log V)	O(E log V) (PQ 기반)	O(E log V)
그래프 밀도에 따른 성능	희소 그래프에서 유리	조밀 그래프에서 유리	중간~조밀, 대규모에 적합
정점 수 V 영향	log V (via 간선 정렬)	log V (via PQ)	log V (병합 단계 수)
간선 수 E 영향	직접적 영향 큼 (정렬 대상)	비례 증가	반복마다 전역 간선 스캔 필요 → E가 크면 느려짐
병렬화 가능성	중간 (간선 정렬, 병합 병렬화 일부 가능)	낮음 (우선순위 큐, 연속 의존)	높음 (각 컴포넌트 독립적으로 동작 가능)
Greedy 특성	전역 최적 간선 순차 선택	지역 최적 간선 선택	병렬 Greedy (로컬 최적 간선 병합)
초기 조건	전체 간선이 필요함	시작 정점 1개만 필요	전체 정점 필요, 각자 컴포넌트로 시작
적용 예시	간단한 네트워크 문제	실시간 최적경로 확장, 조밀 연결망 분석	대규모 네트워크, 병렬 환경, 분산 그래프 처리
코드 복잡도	낮음 (간단한 정렬+Union-Find)	중간 (PQ + 정점 상태 추적)	높음 (반복적 병합, 자료구조 동기화 필요)

 자 그럼, 상황마다 최적의 알고리즘을 알게되었다. 크루스칼은 간선이 적을때 유리하고, 프림은 간선 밀도가 높을때 유리하고, 보루프카는 병렬 작업에 유리하다. 이를 검증하기 위한 테스트 파일을 작성하고 결과를 비교해보자. 실행 시간 평균과 표준편차, 힙 메모리 사용량을 측정할 것이다. 실험 환경은 노드 수, 간선 수, 직/병렬 여부에 따라 측정되었다. 프림의 경우 노드관점 탐색이므로 병렬 측정은 제외했다. 다용도 환경에서 작성되었으므로 측정이 불안정할 수 있다.

• 코드(GPT로 작성되어 잘못된 정보가 있을 수 있음)

  import java.util.*;
  import java.util.concurrent.atomic.*;
  
  public class MSTBenchmark {
  
      // JVM 실행 시 아래 옵션을 사용하세요.
      // java -Xms4g -Xmx4g -XX:+UseG1GC MSTBenchmarkOptimized
  
      static class Edge implements Comparable<Edge> {
          int u, v, w;
          Edge(int u, int v, int w) { 
              this.u = u; 
              this.v = v; 
              this.w = w; 
          }
          public int compareTo(Edge o) { 
              return this.w - o.w; 
          }
      }
  
      static class UnionFind {
          int[] parent, rank;
          UnionFind(int n) {
              parent = new int[n];
              rank = new int[n];
              for (int i = 0; i < n; i++) 
                  parent[i] = i;
          }
          int find(int x) { 
              return parent[x] == x ? x : (parent[x] = find(parent[x])); 
          }
          void union(int a, int b) {
              a = find(a); 
              b = find(b);
              if (a == b) return;
              if (rank[a] < rank[b]) 
                  parent[a] = b;
              else if (rank[a] > rank[b]) 
                  parent[b] = a;
              else {
                  parent[b] = a; 
                  rank[a]++;
              }
          }
      }
  
      // 간선 리스트를 만들 때, 초기 용량을 E로 설정하여 내부 배열 재할당을 피함.
      static List<Edge> genEdges(int V, int E) {
          Random rnd = new Random(0);
          List<Edge> edges = new ArrayList<>(E);
          for (int i = 0; i < E; i++) {
              int u = rnd.nextInt(V), v = rnd.nextInt(V), w = rnd.nextInt(1000) + 1;
              if (u != v)
                  edges.add(new Edge(u, v, w));
          }
          return edges;
      }
  
      static long kruskalSingle(List<Edge> edges, int V) {
          Collections.sort(edges);
          UnionFind uf = new UnionFind(V);
          for (Edge e : edges)
              if (uf.find(e.u) != uf.find(e.v))
                  uf.union(e.u, e.v);
          return 0;
      }
  
      static long kruskalParallel(List<Edge> edges, int V) {
          Edge[] arr = edges.toArray(new Edge[0]);
          Arrays.parallelSort(arr);
          UnionFind uf = new UnionFind(V);
          for (Edge e : arr)
              if (uf.find(e.u) != uf.find(e.v))
                  uf.union(e.u, e.v);
          return 0;
      }
  
      // Prim: 각 정점의 인접 간선 리스트를 만들 때, 예상 간선 수 = (E * 2)/V 로 초기 용량 설정
      static long prim(List<Edge> edges, int V, int E) {
          int expectedEdgeCount = Math.max(4, (E * 2) / V);
          List<List<int[]>> adj = new ArrayList<>(V);
          for (int i = 0; i < V; i++)
              adj.add(new ArrayList<>(expectedEdgeCount));
          for (Edge e : edges) {
              adj.get(e.u).add(new int[]{e.v, e.w});
              adj.get(e.v).add(new int[]{e.u, e.w});
          }
          boolean[] used = new boolean[V];
          int[] dist = new int[V];
          Arrays.fill(dist, Integer.MAX_VALUE);
          dist[0] = 0;
          // PriorityQueue의 초기 용량을 V로 설정
          PriorityQueue<int[]> pq = new PriorityQueue<>(V, Comparator.comparingInt(a -> a[1]));
          pq.add(new int[]{0, 0});
          while (!pq.isEmpty()) {
              int u = pq.poll()[0];
              if (used[u]) continue;
              used[u] = true;
              for (int[] nei : adj.get(u)) {
                  if (!used[nei[0]] && nei[1] < dist[nei[0]]) {
                      dist[nei[0]] = nei[1];
                      pq.add(new int[]{nei[0], nei[1]});
                  }
              }
          }
          return 0;
      }
  
      static long boruvkaSingle(List<Edge> edges, int V) {
          UnionFind uf = new UnionFind(V);
          int components = V;
          while (components > 1) {
              Edge[] cheapest = new Edge[V];
              for (Edge e : edges) {
                  int u = uf.find(e.u), v = uf.find(e.v);
                  if (u != v) {
                      if (cheapest[u] == null || e.w < cheapest[u].w)
                          cheapest[u] = e;
                      if (cheapest[v] == null || e.w < cheapest[v].w)
                          cheapest[v] = e;
                  }
              }
              for (Edge e : cheapest) {
                  if (e != null) {
                      int u = uf.find(e.u), v = uf.find(e.v);
                      if (u != v) { uf.union(u, v); components--; }
                  }
              }
          }
          return 0;
      }
  
      static long boruvkaParallel(List<Edge> edges, int V) {
          UnionFind uf = new UnionFind(V);
          int components = V;
          while (components > 1) {
              @SuppressWarnings("unchecked")
              AtomicReference<Edge>[] cheapest = new AtomicReference[V];
              for (int i = 0; i < V; i++) 
                  cheapest[i] = new AtomicReference<>();
              edges.parallelStream().forEach(e -> {
                  int u = uf.find(e.u), v = uf.find(e.v);
                  if (u != v) {
                      cheapest[u].updateAndGet(cur -> cur == null || e.w < cur.w ? e : cur);
                      cheapest[v].updateAndGet(cur -> cur == null || e.w < cur.w ? e : cur);
                  }
              });
              for (AtomicReference<Edge> ref : cheapest) {
                  Edge e = ref.get();
                  if (e != null) {
                      int u = uf.find(e.u), v = uf.find(e.v);
                      if (u != v) { uf.union(u, v); components--; }
                  }
              }
          }
          return 0;
      }
  
      // 메모리 사용량과 실행 시간을 측정하는 메서드
      static void runAndRecord(String name, Runnable task, List<Long> times, List<Double> mems) {
          System.gc();
          // 현재 힙 사용량 (바이트 단위)
          long beforeMem = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
          long start = System.nanoTime();
          task.run();
          long elapsed = (System.nanoTime() - start) / 1_000_000; // ms 단위
          long afterMem = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
          times.add(elapsed);
          mems.add((afterMem - beforeMem) / (1024.0 * 1024.0)); // MB 단위
      }
  
      static void benchmark(int V, int E, int runs) {
          // 간선 리스트를 생성할 때 예상 용량을 지정
          List<Edge> base = genEdges(V, E);
          Map<String, List<Long>> times = new LinkedHashMap<>();
          Map<String, List<Double>> mems = new LinkedHashMap<>();
          String[] algos = { "Kruskal(single)", "Kruskal(parallel)", "Prim(single)" };
          for (String a : algos) {
              times.put(a, new ArrayList<>());
              mems.put(a, new ArrayList<>());
          }
          if (E <= 200_000) {
              times.put("Boruvka(single)", new ArrayList<>());
              mems.put("Boruvka(single)", new ArrayList<>());
              times.put("Boruvka(parallel)", new ArrayList<>());
              mems.put("Boruvka(parallel)", new ArrayList<>());
          }
  
          for (int i = 0; i < runs; i++) {
              // 매 실행마다 동일한 간선 리스트의 복사본 사용
              List<Edge> copy = new ArrayList<>(base);
              runAndRecord("Kruskal(single)", () -> kruskalSingle(new ArrayList<>(copy), V), times.get("Kruskal(single)"), mems.get("Kruskal(single)"));
              runAndRecord("Kruskal(parallel)", () -> kruskalParallel(new ArrayList<>(copy), V), times.get("Kruskal(parallel)"), mems.get("Kruskal(parallel)"));
              runAndRecord("Prim(single)", () -> prim(new ArrayList<>(copy), V, E), times.get("Prim(single)"), mems.get("Prim(single)"));
              if (E <= 200_000) {
                  runAndRecord("Boruvka(single)", () -> boruvkaSingle(new ArrayList<>(copy), V), times.get("Boruvka(single)"), mems.get("Boruvka(single)"));
                  runAndRecord("Boruvka(parallel)", () -> boruvkaParallel(new ArrayList<>(copy), V), times.get("Boruvka(parallel)"), mems.get("Boruvka(parallel)"));
              }
          }
  
          System.out.printf("Config: V=%d, E=%d, Runs=%d%n", V, E, runs);
          times.keySet().forEach(name -> {
              double avgTime = times.get(name).stream().mapToLong(x -> x).average().orElse(0);
              double stdTime = Math.sqrt(times.get(name).stream().mapToDouble(x -> Math.pow(x - avgTime, 2)).sum() / runs);
              double avgMem = mems.get(name).stream().mapToDouble(x -> x).average().orElse(0);
              double stdMem = Math.sqrt(mems.get(name).stream().mapToDouble(x -> Math.pow(x - avgMem, 2)).sum() / runs);
              System.out.printf("%-20s: time=%.2f±%.2f ms, mem=%.2f±%.2f MB%n", name, avgTime, stdTime, avgMem, stdMem);
          });
          System.out.println();
      }
  
      public static void main(String[] args) {
          int V = 2000, runs = 5;
          int[][] configs = { { V, 5 * V }, { V, 20 * V }, { V, 100 * V } };
          for (int[] cfg : configs) {
              benchmark(cfg[0], cfg[1], runs);
          }
      }
  }
  

MST 알고리즘 벤치마크 결과 (V=2000, Runs=5)

알고리즘	E=10,000시간(ms)	E=10,000 메모리(MB)	E=40,000 시간(ms)	E=40,000 메모리(MB)	E=200,000 시간(ms)	E=200,000 메모리(MB)
크루스칼 (단일)	3.40 ± 1.02	1.00 ± 0.00	7.40 ± 1.36	1.00 ± 0.00	36.40 ± 1.96	1.76 ± 0.00
크루스칼 (병렬)	5.00 ± 0.89	3.20 ± 0.40	18.20 ± 8.13	10.60 ± 0.49	12.60 ± 16.21	20.40 ± 0.80
프림 (단일)	3.00 ± 1.90	1.40 ± 0.80	2.20 ± 0.40	3.00 ± 0.00	8.40 ± 1.02	14.00 ± 0.00
보르푸카 (단일)	1.00 ± 1.55	1.00 ± 0.00	1.00 ± 0.00	1.00 ± 0.00	6.00 ± 0.00	1.00 ± 0.00
보르푸카 (병렬)	6.60 ± 7.14	24.00 ± 3.29	3.00 ± 0.00	22.40 ± 0.80	13.00 ± 0.63	22.40 ± 0.49

 단일 버전 크루스칼은 메모리 사용이 일관되게 낮지만 조밀해질수록 시간 증가폭이 커져 대규모 그래프에서 느린 편이다. 병렬 버전은 고밀도에서 평균 실행시간이 개선되나 표준편차가 매우 커 안정성이 떨어지며 메모리 소비도 크게 늘어난다.

 프림은 모든 밀도에서 실행시간이 안정적이고 빠르며, 특히 중간 밀도에서 최저 시간을 기록했다. 하지만 높은 밀도에서 메모리 사용량이 크게 증가해 메모리 예산이 고려된다.

 단일 버전 보르푸카는 실행 시간과 메모리 모두 일관되게 낮아 가장 안정적이면서 빠른 성능을 나타낸다. 병렬 버전은 오버헤드로 희소 구간에서는 성능저하가 나탄나지만, 중-고밀도 구간에서 단일 버전 대비 약간의 시간 이득을 보지만 메모리 사용량이 급증하는 부하가 있다.

 정리하자면, 조밀한 그래프에서는 프림이 최고이며, 전체적으로 일관된 성능은 단일 보르푸카를 선택하는 것이 좋다. 병렬 크루스칼은 고밀도 작업에서는 고려할 수 있겠지만, 변동성이 크므로 조심해서 써야 한다.