1

グラフとその操作方法について独学するために、いくつかのアルゴリズムを実装しています。Javaでそれを行うための最良の方法は何ですか?

有向グラフと加重有向グラフの短い非常に単純なクラス定義について、簡単なヘルプを提供できるかどうかを尋ねたかっただけです。

私はウェブを見ましたが、それを実装したくありません。クラスの簡単な定義だけです....使用するのに最適なデータ構造は何だと思いますか? 隣接リスト?

無向グラフの場合、次のように定義しました。

public interface Graph { 
  Collection vertices();  // returns a collection of all the 
        //   Vertex objects in the graph 
  Collection edges();  // returns a collection of all the 
     //   Edge objects in the graph 
  Collection incidentEdges(Vertex v); // returns a collection of  
       //   Edges incident to v 
  boolean isAdjacent(Vertex v, Vertex w); // return true if v and     
}                 //   w are adjacent 

public class Vertex { 
  public boolean visited;  // initially false for all vertices 
} 

public class Edge { 
  Vertex v1, v2;     // undirected edge 
  Vertex opposite(Vertex v); // given a vertex return the one 
}          // at the other end of this edge
4

2 に答える 2

1

これは単純な実装です (これは、多くの基本的なユースケースには十分なはずです)。

public class Graph { 
  public List<Node> nodes = new ArrayList<Node>();
}                

public class Node{
  public List<Node> neighbors = new ArrayList<Node>();
 //here you can add stuff like "public boolean visited;", if your algorithm requires it
}

(これは単なる例です。グラフ構造を実装する方法はたくさんあります)。

于 2013-02-17T14:22:35.890 に答える
0

使用するデータ構造は、コードの目的によって異なります... 通常、リストは非常にうまく機能しますが、グラフが高度に接続されている (ほとんどのノードがほとんどのノードに接続されている) 場合、リストは扱いにくく、通常、ある種の行列が優先されます。

たとえば、行列を使用するには、ノードのベクトルを保持してから、整数の 2 次元ベクトルを使用してノードを参照します。

また、軽量クラスを作成するために、ノードのクラスを宣言する必要はありません。ノードとエッジを追加するための関数を提供でき、そのような要素を整数で識別できます。

それらをサブクラス化する予定がある場合は、Node クラスまたは Edge クラスを持つことが適している場合があります (たとえば、グラフを表示する GUI を実行する場合に役立つ可能性があります)。より簡単です。

于 2013-02-17T14:41:46.153 に答える