按模式进行图形搜索

Question

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

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

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

搜索 (A、B、C) 应该 return 所有 ID，以防节点类型在此方向连接。 Return 可以是 [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);

List<String> typePattern = new ArrayList<String>();
typePattern.add("A");
typePattern.add("B");
typePattern.add("C");
// typePattern.add("D");


Graph<Integer, String> graph = new Graph<Integer, String>();
List<List<String>> resutls = graph.search(vertex1, typePattern);

assertResults(resutls, expectedAnswers);

Answer 1

以你的例子为例：

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

按模式进行图形搜索

Graph search by pattern

java

algorithm

graph

path-finding