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

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

我已将文本文件解析为所有行（包括空白行）的 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 有特殊的含义，让我们把它和其他的分开。（即，将其设置为单独的字符串变量，并将其从 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;

我认为应该这样做；现在“节点”包含了整个迷宫，全部连接起来。不过，我在您的代码中发现了一个错误：如果connections.isEmpty()，您的isConnected() 函数应该返回false，而不是如果它为null。它永远不应该为空，因为您在构造函数中使用新列表对其进行了初始化。

于 2011-06-02T04:10:51.803 回答
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 回答
0

一种解决方案是使用适当的 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));
}

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

于 2011-06-02T04:05:06.283 回答