java - 解析有关有向图的输入

Question

我正在解决一个问题，但遇到了轻微的延迟。我正在使用有向图，并尝试确定是否在某个输入内，是否存在到达那里的路线。现在我的问题是我必须在一个字符串中输入输入，但必须以提取重要信息的方式对其进行解析。例如:

您有一个问题实例，其中 G 是一个有向图，具有从 s 到 t(节点)的路径

我的输入字符串将是:(1,2,3,4,5),((1,2),(1,3),(2,3),(2,4),(3,2),(3,5),(4,3),(5,2)),1,5

第一组括号代表节点，第二组括号代表图和路线的组成，其中数字 1 代表 s，5 代表 t(最后两个数字)。

我必须实现一个程序来确定路径是否存在。但问题出在解析上。我需要提取节点列表(第一个括号)、边列表(第二组)、起始节点(1)和结束节点(5)。

任何人都可以向我提供一些有关如何解析这些内容并以可以提取和打印这些内容的方式分解它们的见解吗？我并不是在寻找一个完整的书面工作程序，只是澄清，也许还有代码片段来为我指明正确的方向。任何帮助将不胜感激。

Answer 1

如果我们假设输入严格遵循您提供的格式，那么这只是一个解析问题。以下是获取三个大块(顶点、边和 st)的方法。

 String input=" (1,2,3,4,5),((1,2),(1,3),(2,3),(2,4),(3,2),(3,5),(4,3),(5,2)),1,5";

String nodes=input.substring(0, input.indexOf("((")-1).trim();
String edges=input.substring(input.indexOf("((")+1, input.indexOf("))")+1).trim();
String st=input.substring(input.indexOf("))")+3).trim();

然后您可以单独解析每个 block 并获取其值。有一件事:边列表足以定义图形(您实际上不需要第一个 block )。

编辑: 您可以简单地初始化一个 boolean 数组 visited[] ，其大小等于顶点数。最初，并未访问所有顶点。