英文:
Graph Transitivity Java
问题
我正在使用自定义图形来表示一组数据，如图所示：
我已经创建了几种方法，允许我填充这个结构。这种表示方法的主要目标是能够快速判断特定路径是否存在。我在路径搜索方法方面遇到了以下问题：
例如，如果我考虑路径 "A->D->X"、"B->D->#"、"A->E->#"、"A->D->#"，我希望能够获得路径的存在情况。
然而，如果我考虑路径 "B->D->X"，我希望得到路径不存在的结果。
您对于开发这种类型的方法是否有任何建议，而无需考虑初始数据集？
英文:
I'm using a custom graph to represent a set of data, as shown in the figure:
I have already created several methods that allow me to fill the structure. The main objective of this type of representation is to know quickly if a specific path exists. I have the following problem with the path search method:
For example, if I consider the paths "A-> D-> X", "B-> D -> #", "A-> E -> #", "A-> D -> #", then I would like to obtain the existence of the paths.
However, if I consider the path "B -> D -> X", I would like to get that the path does not exist.
Do you have any suggestions for developing this type of method without considering the initial data set?
答案1
得分: 2
如果您的表中仅提供了可用路径，您可以使用任何实现集合数据结构的方法，例如Java中的HashSet或TreeSet。只需将所有路径添加到集合中，然后使用Set.contains方法来检查路径是否有效。
只要有效路径较短或数量较少，这种方法就能够正常工作。如果路径数量很大且较长，则使用其他数据结构可以获得更好的性能。
例如，字典树（Trie）是一种用于存储序列项的集合，可让您在时间复杂度与序列长度成比例的情况下检查序列是否存在。传统上它常用于处理字符串，但您也可以轻松地将其用于图路径。在这种用法中，字典树中的节点将存储您的图的节点，因此字典树中的路径对应于图中的有效路径。
英文:
If the only available paths are the ones in your table, you can use any implementation of a set data structure, like HashSet or TreeSet in Java. Just add all the paths to the set, and then use the Set.contains method to check if a path is valid.
This will work reasonably well as long as the valid paths are short or there is a small number of them. If there is a large number of paths, and they are long, you'll get better performance with other data structures.
For example a trie is a collection for sequences of items, that lets you check if a sequence is present in time proportional to the length of the sequence. It has been traditionally used for strings, but you can easily use it for graph paths. In this usage, the nodes in the trie would store nodes of your graph, so that a path in the trie corresponds to a valid path in your graph.
答案2
得分: 0
做出以下两个假设：
- 边是双向的；
- 不同于您列出的示例，您不仅寻找三节点（或两边）的路径，意味着
A->E->#->D->B也是一条有效路径，应该返回 true。
不相交集合/并查集数据结构 正好提供了这种能力。
在这个数据结构中，有多种底层实现，所有连接的节点都将在同一个集合中。因此，如果您有 n 个连接组件，则会有相同数量的不相交集合。
要确定节点1和节点2之间是否存在路径，只需查看它们是否在同一个集合中。
英文:
Making two assumptions here:
- The edges are bidirectional;
- Unlike the examples you have listed, you are not looking for 3-node (or 2-edge) paths only, meaning
A->E->#->D->Bis also a valid path and should return true.
The Disjoint Sets / Union-Find Data Structure gives you just that ability.
In this DS, which has more than one underlying implementations, all connected nodes will be in the same set. Thus If you have n connected components, then you will have as many disjoint-sets.
To find if there is a path between node-1 and node-2, just see if they are in the same set.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论