按模式搜索图表

Question

您能否给出我可以学习如何通过某种模式在图形中搜索的方向。

我有一些具有唯一 ID 和类型的单向图，例如 A、B、C。

我需要根据模式搜索所有 ID。例如

如果节点类型在此方向连接，搜索 ( A, B, ) 应返回所有 ID。C返回可以是 as[1,4,6] [4,6,8]等。

当我在寻找某种特定类型的节点时，Bfs 和 dfs 可能会有所帮助，但是如果我有这些节点之间的连接模式，我该如何搜索。

我的测试如下所示：

Vertex<Integer, String> vertex1 = new Vertex<Integer, String>(1, "A");

Vertex<Integer, String> vertex2 = new Vertex<Integer, String>(2, "B");

Vertex<Integer, String> vertex3 = new Vertex<Integer, String>(3, "D");

Vertex<Integer, String> vertex4 = new Vertex<Integer, String>(4, "A");

Vertex<Integer, String> vertex5 = new Vertex<Integer, String>(5, "C");

Vertex<Integer, String> vertex6 = new Vertex<Integer, String>(6, "B");

Vertex<Integer, String> vertex7 = new Vertex<Integer, String>(7, "E");

Vertex<Integer, String> vertex8 = new Vertex<Integer, String>(8, "C");

vertex1.setNeighbors(Collections.singletonList(vertex2));

vertex2.setNeighbors(Arrays.asList(vertex3, vertex5));

vertex3.setNeighbors(Collections.singletonList(vertex2));

vertex4.setNeighbors(Arrays.asList(vertex5, vertex6, vertex7));

vertex5.setNeighbors(Arrays.asList(vertex2, vertex4, vertex6));

// vertex5.setNeighbors(Arrays.asList(vertex2, vertex3, vertex4, vertex6));

vertex6.setNeighbors(Arrays.asList(vertex4, vertex5, vertex8));

vertex7.setNeighbors(Collections.singletonList(vertex4));

vertex8.setNeighbors(Collections.singletonList(vertex6));

List<List<String>> expectedAnswers = new ArrayList<List<String>>();

List<String> answer = new ArrayList<String>();

answer.add("1");

answer.add("2");

answer.add("5");

expectedAnswers.add(answer);

answer = new ArrayList<String>();

answer.add("4");

answer.add("6");

answer.add("5");

expectedAnswers.add(answer);

answer = new ArrayList<String>();

answer.add("4");

answer.add("6");

answer.add("8");

expectedAnswers.add(answer);

Answer 1

至于你的例子：使用 BFS 或 DFS 查找所有 A。将找到的任何“A”添加到某个容器 C1。对于 C1 中的每个元素，检查它是否有“B”个邻居。将找到的任何“AB”路径添加到 C2。对于 C2 中的每个元素，检查其最后一个节点是否有“C”个邻居。将找到的任何“ABC”路径添加到 C3。报告 C3 中的所有元素