10

外部ライブラリを使用できないので、自分でデータ構造を構築する方法を考えています。私は多分このようなことを考えていました：

public class Node{
    Set<Edge> adjacent;
    int value;
}

public class Edge{
    Node target;
    int weight;
}

しかし、おそらくもっと良い方法があると思います。

このグラフの最終的な使用法は、その上でベルマンフォードアルゴリズムを実行することですが、明らかに最初に機能するグラフが必要です。

4

3 に答える 3

14

答えは、グラフに適用することを計画しているアルゴリズムに大きく依存します。

グラフを表す一般的な方法は、隣接リストと隣接行列の2つです。あなたの場合、隣接行列は重みを表す整数の正方配列です。表現は隣接リストを使用します。

隣接行列でより適切に機能するアルゴリズムがあります（たとえば、Floyd-Warshallアルゴリズム）。他のアルゴリズムは、隣接リストでより適切に機能します（たとえば、ダイクストラのアルゴリズム）。グラフがまばらな場合、隣接行列の使用は禁止される可能性があります。

于 2012-11-19T03:53:02.187 に答える
4

いつものように、グラフを隣接リストまたは隣接行列として表すことができます。選択は本当にあなたの問題の詳細に依存します。

隣接行列を使用すると、重みを表す整数の行列を作成できます。

隣接リストを使用する場合は、これまでと同様に、整数のリストのリストを保存するだけで済みます（グラフのノードが整数値で識別されていると仮定します）。

于 2012-11-19T03:49:34.517 に答える
1

重み付けされていないグラフのようにノードを使用して、ノードが接続されているノードのリストを保持し、さらに接続に関連付けられた重みを次のように追加できます。

public class Node{
    int value;
    HashMap<Node,Integer> adjacency;
}
于 2014-11-11T05:15:52.623 に答える