java - 将txt文件转换为邻接表，然后制作Graph

Question

我正在做一个广度优先搜索程序，它将读取邻接列表类型的文本文件，然后相应地对其执行 BFS。我在读取文本文件，然后将其添加为节点数组列表时遇到问题。

如何让它正确读取每一行并关联其连接？

我通过在主程序中手动添加节点，然后制作图表并对其执行 BFS 来测试我的程序。

这是我的 Node 类:

import java.util.*;

public class Node {

        public String data; // data element
        public boolean visited=false; // flag to track the already visited node
        public List<Node> adjacentNodes = new LinkedList<Node>(); // adjacency list
//      public List adjacentNodes = new LinkedList(); // adjacency list
        public Node rootNode;

        public Node(String data){
            this.data = data;
        }

        public void addAdjacentNode(final Node node){
            adjacentNodes.add(node);
            node.adjacentNodes.add(this);
//          adjacentNodes.add(rootNode);
//          node.adjacentNodes.add(this)
        }

    }

这是我的 Graph 类:(我尝试在我的文本文件中读取的内容位于我的主文件中)

import java.io.File;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.*;


/*- enqueue the start node to a Queue
- make the start node as visited
- while queue is not empty
  - dequeue the node lets say u
  - print or whatever you want to
  - for every adjacent node v of u
      - if v is not already visited
          - mark v as visited
          - enqueue v to the Queue*/
public class Graph {

    public List nodes = new ArrayList();

    public void breadthFirstTraversal(Node rootNode){
        Queue<Node> q = new LinkedList<Node>();
//      Queue q = new LinkedList();
        q.add(rootNode);
        System.out.print(rootNode.data + " ");
//      printNode(rootNode);
        rootNode.visited=true;
        while(!q.isEmpty()){
            Node n = (Node)q.poll();
            System.out.print(n.data + " ");
            for(Node adj : n.adjacentNodes){
                if(!adj.visited){
                    adj.visited=true;
                    q.add(adj);
                }
            }
            clearNodes();
        }

    }

    private void clearNodes() {
        // TODO Auto-generated method stub
        nodes = null;   //clear nodes and set to null
    }

/*  private void printNode(Node node) {
        // TODO Auto-generated method stub
        System.out.print(node);
    }*/

    public static void main(String[] args) throws FileNotFoundException {

        Graph g = new Graph();

        Scanner scan = new Scanner(new File("Connections.txt"));   // scanner to read file
        String line = scan.nextLine();                        // read first line
        int nbLine = Integer.parseInt(line);                  // get number of lines
        ArrayList<int[]> al = new ArrayList<int[]>();        
        for(int i = 0; i < nbLine; i++) {                     // read each line
           line = scan.nextLine();
           String[] token = line.split(" ");                  // split each number into different String
           int[] points = new int[token.length - 1];          // prepare array of int[] - 1
//         int[] point = new int[];
           int[] point = new int[token.length];
        for(int j = 0; j < token.length; j++){              // skip first one
             points[j-1] = Integer.parseInt(token[j]);       // store as int
           al.add(points);                                    // save in ArrayList
        }


/*      Scanner s = new Scanner(new File("C:/Users/cantuj3/Documents/Ass 2/Connections.txt"));
        ArrayList<Node> list = new ArrayList<Node>();
        while (s.hasNext()){
            g.nodes.add(s.next());
            //list.add(g);
        }       
        s.close();*/



/*      Node frankfurt = new Node("frankfurt");
        Node mannheim = new Node("mannheim");
        Node wurzburg = new Node("wurzburg");
        Node stuttgard = new Node("stuttgard");
        Node kassel = new Node("kassel");
        Node karlsruhe = new Node("karlsruhe");
        Node erfurt = new Node("erfurt");
        Node numberg = new Node("numberg");
        Node augsburg = new Node("augsburg");
        Node munchen = new Node("munchen");

        Graph g = new Graph();

        g.nodes.add(frankfurt);
        g.nodes.add(mannheim);
        g.nodes.add(wurzburg);
        g.nodes.add(stuttgard);
        g.nodes.add(kassel);
        g.nodes.add(karlsruhe);
        g.nodes.add(erfurt);
        g.nodes.add(numberg);
        g.nodes.add(augsburg);
        g.nodes.add(munchen);

        frankfurt.addAdjacentNode(mannheim);
        frankfurt.addAdjacentNode(wurzburg);
        frankfurt.addAdjacentNode(kassel);

        mannheim.addAdjacentNode(karlsruhe);

        karlsruhe.addAdjacentNode(augsburg);

        augsburg.addAdjacentNode(munchen);

        munchen.addAdjacentNode(kassel);
        munchen.addAdjacentNode(numberg);

        wurzburg.addAdjacentNode(erfurt);
        wurzburg.addAdjacentNode(numberg);

        numberg.addAdjacentNode(stuttgard);
        g.breadthFirstTraversal(frankfurt);*/
    }

}

这是我的输入文件:

01 02
02 01 03
03 02 04 05
04 03
05 03 06
06 05

这是我在 main 中自己编写的代码块:

        Scanner scan = new Scanner(new File("Connections.txt"));   // scanner to read file
        String line = scan.nextLine();                        // read first line
        int nbLine = Integer.parseInt(line);                  // get number of lines
        ArrayList<int[]> al = new ArrayList<int[]>();        
        for(int i = 0; i < nbLine; i++) {                     // read each line
           line = scan.nextLine();
           String[] token = line.split(" ");                  // split each number into different String
           int[] points = new int[token.length - 1];          // prepare array of int[] - 1
//         int[] point = new int[];
           int[] point;
        for(int j = 0; j < token.length; j++){              // skip first one
             points[j-1] = Integer.parseInt(token[j]);       // store as int
           al.add(points);                                    // save in ArrayList
        }

我走在正确的道路上吗？

Answer 1

您的基本步骤需要是:

1. 读取文件的一行
2. 将该行变成一个对象
3. 将该对象添加到集合中
4. 重复此操作，直到没有更多行可供阅读

由于我不想为您做您的工作，所以我会给您留下一些示例:

读取文件的一行

String line = reader.readLine(); // in this case, 'reader' will be a BufferedReader referencing your file

将该线变成一个对象

这取决于您的输入文件格式。举个例子，如果我的输入是这样的:

first_thing 10
second_thing 20
third_thing 30
...

那么我可以这样做:

String[] components = line.split(" ");
if (components.length == 2) {
    MyCustomObject myCustomObject = new MyCustomObject(components[0], components[1]);
}

将该对象添加到集合

String[] components = line.split(" ");
if (components.length == 2) {
    MyCustomObject myCustomObject = new MyCustomObject(components[0], components[1]);
    myCollection.add(myCustomObject); // you can choose the type of collection here
}

重复，直到没有更多的行可供阅读

while ( (line = reader.readLine()) != null ) {
    ...
} 

希望这有帮助!