一个顶点,多个出口,有向有环图,环遍历深度为1,给出能遍历出这张图所有可执行链路的java8代码
时间: 2023-10-15 16:02:03 浏览: 116
MSRC-9数据集 图神经网络
假设图的顶点类型为`Vertex`,每个顶点有一个`List<Vertex>`类型的成员变量表示其出边集合。那么可以使用深度优先搜索(DFS)来遍历图,并记录所有可执行链路。
以下是使用Java 8的lambda表达式实现的代码:
```
public static List<List<Vertex>> findAllPaths(Vertex start) {
List<List<Vertex>> allPaths = new ArrayList<>();
List<Vertex> curPath = new ArrayList<>();
dfs(start, curPath, allPaths);
return allPaths;
}
private static void dfs(Vertex cur, List<Vertex> curPath, List<List<Vertex>> allPaths) {
curPath.add(cur);
if (cur.outEdges.isEmpty()) {
// 当前顶点没有出边,说明到达了一个终止状态,将当前链路加入所有链路中
allPaths.add(new ArrayList<>(curPath));
} else {
for (Vertex next : cur.outEdges) {
// 如果下一个顶点已经在当前链路中,则说明存在环,跳过该分支
if (!curPath.contains(next)) {
dfs(next, curPath, allPaths);
}
}
}
curPath.remove(curPath.size() - 1);
}
```
函数`findAllPaths`接受一个起点`start`,返回一个`List<List<Vertex>>`类型的结果,其中每个元素是一条可执行的链路,是一个`Vertex`类型的顶点列表。函数首先初始化一个空链路`curPath`和一个空链路列表`allPaths`,然后调用`dfs`函数进行深度优先搜索,并将所有可执行链路记录到`allPaths`中。
函数`dfs`接受当前顶点`cur`、当前链路`curPath`和所有链路`allPaths`作为参数,并使用递归进行深度优先搜索。首先将当前顶点加入当前链路中,如果当前顶点没有出边,则说明到达了一个终止状态,将当前链路加入所有链路中;否则,对于每个下一个顶点,如果它不在当前链路中,则递归调用`dfs`函数继续搜索。搜索完毕后,将当前顶点从当前链路中移除,以便回溯。
注意,为了避免重复遍历环,函数在遍历下一个顶点之前,先判断下一个顶点是否已经在当前链路中,如果是,则跳过该分支。这样可以保证每条可执行链路只被记录一次。
阅读全文