1

JGraphT で Prim の最小スパニング ツリー アルゴリズムを実装しようとしています。それはどのように見えますか？

私が遭遇した 1 つの問題は、JGraphT が指示どおりにすべてを処理することでした。そのため、リバースするためにいくつかのぎこちない呼び出しを行う必要がg.getEdgeSource(e)ありg.getEdgeTarget(e)、それらがたまたま正しくなかった場合があります。

JGraphT の Fibonacci Heap を使ってこれを最初に実装しようとしましたが、難しすぎたので、通常の 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;
}
4

3 に答える 3

1

私はあなたのアルゴリズムの結果を宿題であった1つの鉱山と比較しました、そしてそれは両方とも同じ最小総重量を与えます、それを維持してください！

于 2010-10-10T18:08:18.190 に答える
0

エッジの数と頂点の数を増やしながら、異なる結果が得られます。戻ってきます...

于 2010-10-10T18:12:00.023 に答える
0

OK、今は問題ないようです。

ところで、私の演習は少しトリッキーでした。実際に最小全域木を見つけるアルゴリズムを書かなければなりませんでしたが、私のアルゴリズムはエッジでの消去によって進めなければなりませんでした。深さ優先トラバーサルを使用してサイクルを見つけ、赤く「色付け」して最も重みのあるエッジを削除するものを書きました..

PRIM alg は、N=200 ノードとさまざまな値 M=(N*(N-1)/k) for k=2,3,4,8 を持つ 4 つのランダムに生成されたグラフの alg と同じ最小合計重みを生成します。エッジの数。

一見、この種のテストはやり過ぎだと思いましたが、そうではありませんでした。

于 2010-10-10T22:59:12.050 に答える