1

私のグラフの実装は、次のハッシュ テーブルです。

public class DiGraphHash{

private int numNodos, numArcos;
private TheList<Nodo> nodos[];
private TheList<Arco> arcos[];
private TheList<Arco> preds[];

}

ここで、TheList は自分で作成したリストです。

Dijkstra のアルゴリズムでは、各ノードのコストとそのノードに到達するためのパスをマップする必要があります。次の2つの配列があります。

   int[] cost = new cost[num_nodes];
   Nodo[] path = new Nodo[num_nodes];

もう 1 つの重要な詳細は、ノードが文字 A、B、C、D になることです。

たとえば、ノードをマッピングするときに、ノード A にコストを割り当てる必要があるとします。配列内の位置を見つけるにはどうすればよいでしょうか?

hashcode % array.length を使用することを考えていましたが、衝突するかどうかはわかりません (1 文字のみになることを考慮してください)

私はコードについて尋ねているのではなく、アイデアが必要です。

4

1 に答える 1

1

2 つのアイデア:

  1. costクラスにフィールドを追加しますNodo。このように、個別のコストの配列を管理するのではなく、ノードの配列を管理するだけで済みます。ノードをインスタンス化するときにコストを割り当て、後で簡単に検索できます。

  2. 2 つの配列よりも優れたデータ構造は、キーがノード自体であり、値がノードのコストであるマップである可能性があります。次に例を示します。

HashMap<Nodo, Integer> nodesToCosts = new HashMap<Nodo, Integer>();

nodes.put(nodeA, new Integer(5));
nodes.put(nodeB, new Integer(20));
nodes.put(nodeC, new Integer(10));
nodes.put(nodeD, new Integer(5));
于 2013-02-23T04:16:30.777 に答える