0

隣接リストとして表される複数の「迷路」を含むテキスト ファイルからグラフを作成する必要があります。リストは次のとおりです。

A,G
A,B,F
B,A,C,G
C,B,D,G
D,C,E
E,D,F,G
F,A,E
G,B,C,E

D,F
A,B,G
B,A,C,E,G
C,B,D,E,G
D,C
E,B,C,G
F,G
G,A,B,C,E,F

F,A
A,B,G
B,A,G
C,D,G
D,C,G
E,F,G
F,E,G
G,A,B,C,D,E,F

各「迷路」の最初の行には、迷路の開始ノード (最初の文字) と迷路の終了ノード (2 番目の文字) が含まれています。

テキスト ファイルをすべての行 (空白行を含む) の ArrayList に解析し、次に行の ArrayLists の ArrayList (個別の迷路のリスト) に解析しました。これを行うには、テキスト全体を空白行で分割しました。私の問題は、ノードクラスを使用してこれらの「迷路」からグラフを作成する方法がわからないことです。ここに私のノードクラスがあります:

package algo2;

import java.util.ArrayList;


public class Node<T>{

    private T value; //this Node<T>'s value
    public ArrayList<Node<T>> connections;
    public boolean isStart;
    public boolean isEnd;
    public boolean visited;

    public Node(T value){
        this.value = value;
        connections = new ArrayList<Node<T>>();
    }

    //returns the value of this Node<T>
    public T getValue(){
        return value;
    }

    //returns true if the node is connected to any other nodes
    public boolean isConnected(){
        if(connections == null){
            return false;
        }
        return true;
    }

    //returns a list of nodes connected to this node
    public ArrayList<Node<T>> getConnections(){
        return connections;
    }

    //sets the node's value
    public void setValue(T value){
        this.value = value;
    }

    //adds a connection from this node to the passed node
    public void connect(Node<T> node){
        connections.add(node);
    }

    public String toString(){
        return value+"";
    }
}

誰かが私を正しい方向に向けることができますか?

4

3 に答える 3

1

迷路を 1 つだけ設定することに集中しましょう。その後、すべての迷路についてこのプロセスを繰り返すことができます。Java 構文に適したアルゴリズムを作成しようとしました。

それで、私が理解しているように、ここに最初の迷路の ArrayList 変数があります...

List<String> preNodes, which contains:
{"A,G", "A,B,F", "B,A,C,G", "C,B,D,G", "D,C,E", "E,D,F,G", "F,A,E", "G,B,C,E"};

最初の String には特別な意味があるため、残りの部分から分離しましょう。(つまり、別の String 変数として設定し、ArrayList から削除します)。

String startAndEnd, which contains: "A,G";
List<String> preNodes, which contains: 
{"A,B,F", "B,A,C,G", "C,B,D,G", "D,C,E", "E,D,F,G", "F,A,E", "G,B,C,E"};

それでは、まず必要なすべてのノードを構築してから、それらをリンクしてみましょう。

//Define container for nodes
HashMap<String, Node> nodes = new HashMap<String, Node>();
//Create a node for each letter
for(String s : preNodes) {
    String nodeName = s.charAt(0) + "";
    nodes.put(nodeName, new Node());
}
//Link them up appropriately
for(String s : preNodes) {
    String[] splitS = s.split(","); //1 letter in each array cell.
    Node current = nodes.get(splitS[0]); //Get the node we're going to link up.
    for(int i=1; i<splitS.length; i++) {
        current.connect(nodes.get(splitS[i]));
    }
}
//Finally, set the start and end Node.
String[] splitStartAndEnd = startAndEnd.split(",");
nodes.get(splitStartAndEnd[0]).isStart = true;
nodes.get(splitStartAndEnd[1]).isEnd = true;

これでうまくいくはずです。現在、「ノード」には迷路全体が含まれており、すべてリンクされています。ただし、コードにバグがありました。 isConnected() 関数は、null の場合ではなく、connections.isEmpty() の場合に false を返す必要があります。コンストラクターで新しいリストを使用して初期化するため、null にすることはできません。

于 2011-06-02T04:10:51.803 に答える
0

1 つの解決策は、適切な Node コンストラクターを使用して入力に split() を使用することです (簡単にするために、パラメーター T を String に置き換えたことに注意してください)。

class Node {
    public String value;
    public String[] connections;
    public boolean visited;

    public Node (String value, String[] connections) {
        this.value = value;
        this.connections = connections;
        visited = false;
    }

    public boolean isConnected(Node that) {
        boolean res = false;
        for (int i=0; !res && i<this.connections.length; i++) {
            res = (this.connections[i] == that.value);
        }
        return res;
    }

    // more stuff ... :)
}

//read start, end nodes

ArrayList<Node> nodes = new ArrayList<Node>();
for (each line in maze) {
    String[] nodeList = line.split(",");
    nodes.add(nodeList[0], Arrays.copyOfRange(nodeList, 1, nodeList.length));
}

これは、アプリケーションの残りの部分で 2 つのノードが接続されているかどうか、または 1 つがアクセスされているかどうかを簡単に確認できる限り、各ノード内のノードのリストを維持しようとするよりも簡単だと思います。(また、開始ノードと終了ノードを追跡するために、Node クラスにさらにコードを追加する必要があることにも注意してください。)

于 2011-06-02T04:05:06.283 に答える
0

迷路を構築するには、別のクラスに追加のコードを記述する必要があります。テキスト入力を受け取り、接続されたノードのセットを出力します。ノード自体は何も「構築」するべきではありません - それらはただのビルディングブロックです。

それらを接続する方法の擬似コードを次に示します。

nameToNodeMap -> dictionary of string to node
for each line in the file
    previous token = null
    loop:
    try to get a token (letter, separated by commas)
    if there was no token
        break out of the loop
    else
        if nameToNodeMap contains that token
            get the node for that token
        else
            create a node
            add it to nameToNodeMap, with the token as the key
        if previous node != null
            link previous node to this node
        previous nope = current node
        goto loop
于 2011-06-02T03:28:15.203 に答える