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

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

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

Answer 3

ХОРОШО, теперь он выглядит нормально.

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

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

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