1

私はリンクされたデータ構造が初めてで、2次元配列から2つのポイントが与えられ、ポイント間で重みが決定されていないときに無向グラフを作成する方法を考えていました. 私は周りを検索しましたが、探していたものを実際に見つけることができませんでした。

例：

int[][] points = { { 0, 1 },{ 0, 2 },{ 1, 2 },{ 1, 3 },{ 3, 4 } };

引き出すと、このようになります。

      0
      |
    -------
    |     |
    1-----2
    |
    3-----4

編集

また、0 から 4 までの最短経路を見つけ、途中の各移動をカウントしながら、少なくとも 1 回は各ポイントにトラバースできるようにしたいと考えています。後退しなければならない可能性があります。上記の例では、0 ～ 4 の最短パスは (0-2)(2-1)(1-3)(3-4) であり、4 回の移動としてカウントされます。

4

3 に答える 3

2
  1. 隣接するノードのリストを含むクラスNodeを作成します
  2. ポイント配列内のノードを反復処理します。見つけたノードごとに Node オブジェクトを作成します (おそらく、最初にそれらを Map に保持する方がよいでしょう。
  3. もう一度繰り返し、各ノードの隣接ノード リストを埋めます。

このクラス Node を考えてみましょう:

public class Node {
    private int id;
    private List<Node> adjacentNodes = new ArrayList<Node>();

    public List<Node> getAdjacentNodes() {
        return adjacentNodes;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }
}

そして、このメソッドはすべてのノードのコレクションを作成し、それらをリンクします:

 private static Collection<Node> createGraphNodes(int[][] pointsMatrix) {
    Map<Integer, Node> nodes = new HashMap<Integer, Node>();
    for(int[] points: pointsMatrix) {
        for(int point: points) {
            if(nodes.containsKey(Integer.valueOf(point))) {
                continue;
            }

            Node node = new Node();
            node.setId(point);
            nodes.put(point, node);
        }
    }

    for(int[] points: pointsMatrix) {
        int nodeId1 = points[0];
        int nodeId2 = points[1];

        Node node1 = nodes.get(Integer.valueOf(nodeId1));
        Node node2 = nodes.get(Integer.valueOf(nodeId2));

        node1.getAdjacentNodes().add(node2);
        node2.getAdjacentNodes().add(node1);

    }

    return nodes.values();
于 2013-04-07T22:01:27.543 に答える