从文本文件创建迷宫图：Java

Question

我需要从包含多个“迷宫”的文本文件中创建一个图形，这些迷宫表示为邻接列表。名单如下：

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

每个“迷宫”的第一行包含迷宫的起始节点（第一个字母）和结束节点（第二个字母）

我已经将文本文件解析为包含所有行（包括空行）的ArrayList，然后解析为包含行的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+"";
    }
}

有人能给我指一下正确的方向吗

Answer 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"};

因为第一个字符串有一个特殊的含义，让我们把它和其他字符串分开。（即，将其设置为单独的字符串变量，并将其从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;

我认为这应该可以做到；现在“节点”包含了整个迷宫，都连接起来了。不过，我在您的代码中发现了一个bug：如果是连接，isConnected（）函数应该返回false。isEmpty（），如果为null则不为空。它永远不应该为null，因为您在构造函数中使用新列表初始化它

Answer 2

一种解决方案是在输入上使用split（）和适当的节点构造函数（注意，为了简单起见，我用String替换了参数T）：

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));
}

我认为这比在每个节点中维护一个节点列表要简单，只要应用程序的其余部分可以轻松地检查两个节点是否连接或是否访问过一个节点。（还请注意，您可能希望向Node类添加更多代码以跟踪开始和结束节点。）

Answer 3

您应该在单独的类中编写额外的代码来构建迷宫。它将接受文本输入，并输出一组连接的节点。节点本身不应该“构造”任何东西——它们只是构建块

下面是一些如何连接它们的伪代码：

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