java - 图传递 Java

Question

我用的是自定义图来表示一组数据，如图:



我已经创建了几种方法来填充结构。此类表示的主要目标是快速了解特定路径是否存在。我对路径搜索方法有以下问题:

例如，如果我考虑路径“A-> D-> X”、“B-> D -> #”、“A-> E -> #”、“A-> D -> #”，那么我想获得路径的存在。
但是，如果我考虑路径“B -> D -> X”，我想知道该路径不存在。

在不考虑初始数据集的情况下，您对开发此类方法有什么建议吗？

Answer 1

如果唯一可用的路径是表中的路径，则可以使用集合数据结构的任何实现，例如 HashSet或 TreeSet在 java 。只需将所有路径添加到集合中，然后使用 Set.contains检查路径是否有效的方法。

只要有效路径很短或者它们的数量很少，这就会很好地工作。如果有大量路径并且它们很长，则使用其他数据结构可以获得更好的性能。

例如 trie是项目序列的集合，可让您检查序列是否按与序列长度成比例的时间存在。它传统上用于字符串，但您可以轻松地将它用于图形路径。在这种用法中，trie 中的节点将存储图形的节点，以便 trie 中的路径对应于图形中的有效路径。