Java: Как выглядит мой Prim?

Question

Я пытаюсь реализовать алгоритм минимального связующего дерева Prim с JGraphT. Как это выглядит?

Одна проблема, с которой я столкнулся, заключалась в том, что JGraphT обрабатывал все так, как он направлен. Поэтому иногда необходимо сделать несколько неловких звонков, чтобы повернуть вспять g.getEdgeSource(e) а также g.getEdgeTarget(e) если они не оказались правы.

Первоначально я пытался реализовать это с помощью кучи Фибоначчи от JGraphT, но это было слишком сложно, поэтому я просто сделал обычный PQ.

Вместо того чтобы устанавливать веса несуществующих ребер в бесконечность, я просто не добавлял их в очередь.

Совет? Стилистические проблемы? Яркая неэффективность? Код, который я должен использовать вместо того, чтобы использовать свой собственный?

public static Graph<String, DefaultWeightedEdge> primPQ(final WeightedGraph<String, DefaultWeightedEdge> g, String root) {
  Graph<String, DefaultWeightedEdge> mst = new SimpleWeightedGraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class);
  Queue<DefaultWeightedEdge> pq = new PriorityQueue<DefaultWeightedEdge>(g.vertexSet().size(), new Comparator<DefaultWeightedEdge>() {
    @Override
    public int compare(DefaultWeightedEdge o1, DefaultWeightedEdge o2) {
      if (g.getEdgeWeight(o1) < g.getEdgeWeight(o2)) {
        return -1;
      }
      if (g.getEdgeWeight(o1) > g.getEdgeWeight(o2)) {
        return 1;
      } 
      return 0;
    }
  });

  mst.addVertex(root);
  DefaultWeightedEdge link;

  for (String v : g.vertexSet()) {
    link = g.getEdge(root, v);
    if (link != null) {
      pq.add(link);
    }
  }

  //this is made difficult by JGraphT's assumption that everything is directed
  DefaultWeightedEdge minEdge = pq.poll();
  String toAdd;
  String alreadyFound;
  String tmp;

  while (minEdge != null) {
    // guessing at which is in the MST
    toAdd = g.getEdgeTarget(minEdge);
    alreadyFound = g.getEdgeSource(minEdge);

    if (!(mst.containsVertex(toAdd) && mst.containsVertex(alreadyFound))) {
      // swap if backwards
      if (mst.containsVertex(toAdd)) {
        tmp = toAdd;
        toAdd = alreadyFound;
        alreadyFound = tmp;
      }
      mst.addVertex(toAdd);
      mst.addEdge(alreadyFound, toAdd, minEdge);
      System.out.format("%s --> %s\n", g.getEdgeSource(minEdge), toAdd);

      for (String v : g.vertexSet()) {
        if (! mst.containsVertex(v)) {
          link = g.getEdge(toAdd, v);
          if (pq.contains(link)) {
            g.setEdgeWeight(minEdge, Math.min(g.getEdgeWeight(minEdge), g.getEdgeWeight(link)));
          }
          if (link != null && ! pq.contains(link)) {
            pq.add(link);
          }
        }
      }
    }
    minEdge = pq.poll();
  }
  return mst;
}

Answer 1

Я сравнил результат вашего алгоритма с одним моим, который был домашней работой, и он дает одинаковый минимальный общий вес, так держать!

Answer 2

Хорошо, теперь все выглядит хорошо.

Кстати, мое упражнение было немного сложным: мне пришлось написать алгоритм, который действительно находит минимальное остовное дерево, но мой алгоритм должен был действовать путем исключения по краям. Я написал что-то, что сначала использует некоторый обход глубины для нахождения циклов, а затем устраняет наиболее взвешенное ребро, "окрашивая" его в красный цвет.

Ваш PRIM alg дает тот же минимальный общий вес, что и мой alg для 4 случайно сгенерированных графиков, которые имеют N=200 узлов и различные значения M=(N*(N-1)/k) для k=2,3,4,8 для количество ребер.

На первый взгляд, я бы подумал, что такое тестирование было излишним, но это не так!

Answer 3

И при увеличении количества ребер и количества вершин я получаю разные результаты, я вернусь...