树或图数据结构中路径的深度搜索

Question

我正在尝试创建一棵树或一个图形数据结构，如果存在特定的路径，就可以快速搜索(深度搜索)。特别是，从字符串列表开始：

ArrayList<String> data = new ArrayList<String>();
data.add("2.2.3.3.3");
data.add("2.3.4.3.4");
data.add("2.2.2.4.4");

String pathToFind1 = "2.3.4.X.4"
String pathToFind2 = "2.X.X.2.4"
String pathToFind3 = "2.3.X.4.4"

以及要查找的路径(例如，"X.2.X.4.4")，我将检查是否存在这样的路径：

• pathToFind1:连接节点2(深度1)、节点3(深度2)、节点4(深度3)和节点4(深度5)；
• pathToFind2:连接节点2(深度1)、2(深度4)和4(深度5)；
• pathToFind3:连接节点2(深度1)、3(深度2)、4(深度4)和4(深度5)；

值X表示泛型值。

/*
            2
          /   \
         2     3
        / \     \
       2   3     4
      /     \     \  
     4       3     3
      \       \     \     
       4       3     4     
*/

public static boolean findPath(String path) {
    //...
}

findPath(pathToFind1); //return true
findPath(pathToFind2); //return false
findPath(pathToFind3); //return false

我曾经想过使用特瑞，但是这个结构的主要问题是我应该考虑找到一个完整的路径(即包含所有元素的路径)。你能提出一个数据结构或解决方案来解决我的问题吗？注意，没有必要使用树或图，但我的目标是快速搜索路径。

Answer 1

您可以使用两种主要算法来完成这项工作。我指的是DLS和IDS。这两个人是稳定的无意识搜索。这意味着他们在指定的级别上搜索，而不是所有的图形，而且它确实更快，需要更少的内存。试试看他们也许能解决你的问题。