java - 如何使用输入文本文件创建邻接矩阵来表示有向加权图 [java]？

Question

我很难弄清楚如何从输入文件创建邻接矩阵。输入文件应该表示节点的有向加权图。

目的是创建一个可以进行迭代深度优先搜索的程序，但我真的陷入了作业的数据输入部分。

输入文本文件应该如下所示:

每个节点由两行文本表示。例如最上面一行，第一个“S”是节点的名称，第二个“S”表示它是起始节点，第三个“n”表示它是常规节点，而不是目标节点，这将由“g”表示。

第二行是连接到“S”的两个节点，第一个是“B”，加权距离为 1，第二个是“E”，加权距离为 2。

第三行应该是空白，并且模式是重复的。

S S n                     
B 1 E 2            


B N n

C 2 F 3


C N n

D 2 GA 4

D N n

GA 1

E N n

B 1 F 3 H 6

F N n

I 3 GA
 3 C 1

GA N g

H N n

I 2 GB 2 F 1

I N n

GA 2 GB 2

GB N g

我真的被这个问题困住了。我一直在使用缓冲阅读器扫描文件，但我一直想知道使用扫描仪是否会更容易。

我目前正在尝试创建具有名称属性的 Node 对象，并且可能使用某种链接列表创建到其他相邻 Node 对象的链接。我还考虑过使用节点对象数组，但我真的不确定如何表示哪些节点连接到哪些其他节点以及如何使用二维数组将其构建到邻接矩阵中。

任何建议将不胜感激，我是新手，所以如果我的问题对其他人没有学术重要性，我深表歉意

编辑:我的代码是这样的:公共(public)无效actionPerformed(ActionEvent e) {

    if(e.getSource() == openButton)
    {
        returnVal = fileChooser.showOpenDialog(null);

        if(returnVal == JFileChooser.APPROVE_OPTION)
        {
            selected_file = fileChooser.getSelectedFile();

            String file_name = fileChooser.getSelectedFile().getName();
            file_name = file_name.substring(0, file_name.indexOf('.'));

            try
            {
                BufferedWriter buff_writer = null;
                File newFile = new File("."+file_name+"_sorted.txt");           

                boolean verify_creation = newFile.createNewFile();
                //if (verify_creation)
                //  System.out.println("file created successfully");
                //else
                //  System.out.println("file already present in specified location");

                file_reader1 = new BufferedReader(new FileReader(selected_file));
                file_reader2 = new BufferedReader(new FileReader(selected_file));

                FileWriter file_writer = new FileWriter(newFile.getAbsoluteFile());
                buff_writer = new BufferedWriter(file_writer);

                //find the number of nodes in the file
                while( (currentLine = file_reader1.readLine()) != null)
                {
                    k++;
                    System.out.println("value of k: " + k);
                }


                nodeArray = new Node[k];

                while( (currentLine = file_reader2.readLine()) != null) 
                {   
                    //System.out.print(currentLine);

                    String[] var = currentLine.split(" ");


                    nodeArray[x] = new Node(var[0], var[1], var[2]);
                    nodeArray[x].setLink1(new Node(var[3], null, null));



                }

            buff_writer.close();
            file_writer.close();

            }   
            catch (Exception e1)
            {
                e1.printStackTrace();
            }       
        }
    }

编辑#2

我的节点对象看起来像这样:

public Node(String n, String t1, String t2)
{
    name = n;
    type1 = t1;
    type2 = t2;

    link1 = null;
    link2 = null;
    link3 = null;
    link4 = null;
    link5 = null;
    link6 = null;

Answer 1

事情是:你不想想在这里使用二维数组。您想要退后一步，设计/建模适合您正在工作的“实际问题”的类/数据结构。

换句话说:你的问题是关于表示节点和边的图。所以，一些让你继续前进的技巧..

让我们开始:

enum NodeType { START, GOAL, NORMAL ; }

public class Node {
  private final String name;

  public Node(String name) {
    this.name = name;

上面给了你一个合理的方法来区分不同类型的节点。然后我们从节点的表示开始。显然，它的名称是固定的 - 您不想在创建节点后更改其名称。然后你就有像这样的 setter

public void setType(NodeType type) ...

还有更多字段，

private final Map<Node, Integer> neighbors = new HashMap<>();

以及添加新邻居的方法:

public void addNeighborNode(Node node, int weight) {
   neighbors.put(node, weight);

[郑重声明:理论上，您可以创建一个通过构造函数获取所有信息的类，从而避免使用 setter 方法。这有一定的优点，但使事情变得更加复杂；我想...我在这里向您展示的内容已经足够复杂了;-)]

这里的整个想法 - 将解析与表示/构建对象的方式分开。当然，在某些时候您必须读取该字符串，然后从中构建节点对象。

但是你最好从上面这样的 Node 类开始，因为这样你就可以构建一个图表......而不需要解析文本文件:

Node n1 = new Node("n1");
n1.setType(NodeType.START);

Node n2 = new Node("n2");
n2.setType(NodeType.GOAL);

n1.setNeighborNode(n2, 5);

换句话说:首先为图表构建一个漂亮的“类模型”。您可以像上面那样编写测试代码。当这一切都奏效时；然后编写代码来读取该输入文件并将其转换为构建图表所需的方法调用!

长话短说:当然，解析该文本文件很重要，但您不应该不关注这一点。相反:首先仔细考虑数据的类模型。那就是你可以学到最多的东西，并在实验中获得最大的乐趣。拉动绳子，把它们变成物体，这就是“工作”。先玩得开心吧!