java - 从图中的文本文件读取节点数

Question

我想读取文本文件中仅由边组成的节点有多少个。我不想在文本文件的顶部添加来读取顶点数。这是文本文件中包含的内容。

11 3
2 3
0 3
1 4
5 4
5 7
6 7
7 8
8 9
9 10
0 5

问题是我无法从读取文件中获取节点数。我在想是否找到节点的最大值，如果以 0 开头，则加 1。但我仍然无法得到它，所以我尝试读取 nextInt 并与另一个 nextInt 进行比较。这就是我的意思以及到目前为止所做的事情。

public static int readNode(String mazeFile) {
    int numNode = 0;
    File mf = new File(mazeFile);
    try {
        Scanner scan = new Scanner(mf);
        int arc = readLineCount(mf);
        for (int i = 0; i < arc; i++) {
            while (scan.hasNext()) {
                int n1 = scan.nextInt();
                int n2 = scan.nextInt();
                if (n1 > n2) {
                    n2 = n1;
                    numNode = n2;
                } else if (n1 < n2) {
                    n1 = n2;
                    numNode = n1;
                }
            }
        }
    } catch (FileNotFoundException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }
    return numNode;
}

我需要改变什么吗？

Answer 1

使用此方法，您仍然指望用户为图表提供连续的整数节点号。如果图中只有 42 个节点，而有人选择节点号 1111111111 会怎样？要解决此问题，请将节点号视为符号。

import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

class Graph {
  final Set<Integer> nodes = new HashSet<>();
  final Map<Integer, Set<Integer>> edges = new HashMap<>();

  static class Reader {
    String fileName;
    Graph graph;

    Reader(String fileName) {
      this.fileName = fileName;
    }

    Graph read() {
      try {
        return scanGraph();
      } catch (FileNotFoundException ignore) {
        return new Graph();
      }
    }

    Graph scanGraph() throws FileNotFoundException {
      graph = new Graph();
      Scanner scanner = new Scanner(new File(fileName));
      while (scanner.hasNextInt()) {
        int n1 = scanner.nextInt();
        int n2 = scanner.nextInt();
        graph.nodes.add(n1);
        graph.nodes.add(n2);
        addDirectedEdge(n1, n2);
      }
      return graph;
    }

    void addDirectedEdge(Integer n1, Integer n2) {
      if (graph.edges.containsKey(n1)) {
        graph.edges.get(n1).add(n2);
      } else {
        Set<Integer> to = new HashSet<>();
        to.add(n2);
        graph.edges.put(n1, to);
      }
    }    
  }

  interface Visitor {
    void visit(int node);
  }    

  void visitDepthFirst(int start, Visitor visitor) {
    visitDepthFirst(start, visitor, new HashSet<>());
  }

  void visitDepthFirst(int node, Visitor visitor, Set<Integer> visited) {
    visitor.visit(node);
    visited.add(node);
    Set<Integer> successors = edges.get(node);
    if (successors == null) {
      return;
    }
    for (int successor : successors) {
      if (!visited.contains(successor)) {
        visitDepthFirst(successor, visitor, visited);
      }
    }
  }

  public static void main(String [] args) {
    Graph graph = new Graph.Reader(args[0]).read();
    System.out.println("The graph has " + graph.nodes.size() + " nodes:");
    System.out.println(graph.nodes);
    System.out.println("Adjacency list:");
    System.out.println(graph.edges);
    System.out.println("A preorder depth first visit starting from 0:");
    graph.visitDepthFirst(0, new Visitor() {
      @Override
      public void visit(int node) {
        System.out.println("Visiting " + node);
      }
    });
  }
}

我还在您的代码中修复了一些其他有问题的做法。但我没有使用过 Java 8 的功能特性，这会让本文变得不那么冗长。

输出:

The graph has 12 nodes:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Adjacency list:
{0=[3, 5], 1=[4], 2=[3], 5=[4, 7], 6=[7], 7=[8], 8=[9], 9=[10], 11=[3]}
A preorder depth first visit starting from 0:
Visiting 0
Visiting 3
Visiting 5
Visiting 4
Visiting 7
Visiting 8
Visiting 9
Visiting 10

注意，为了简洁起见，我省略了生产 Java 的细节，例如公共(public)/私有(private)和 getter/setter。