在深度优先搜索时,将路径的每条边添加到列表中。
代码示例:
public static void dfs(ArrayList[] adjList, int source, int dest, boolean[] visited, ArrayList curPath, ArrayList> allPaths) {
visited[source] = true;
curPath.add(source);
if (source == dest) {
allPaths.add(new ArrayList<>(curPath));
} else {
for (Integer neighbor : adjList[source]) {
if (!visited[neighbor]) {
dfs(adjList, neighbor, dest, visited, curPath, allPaths);
}
}
}
curPath.remove(curPath.size() - 1);
visited[source] = false;
}
public static ArrayList> findAllPaths(ArrayList[] adjList, int source, int dest) {
ArrayList> allPaths = new ArrayList<>();
boolean[] visited = new boolean[adjList.length];
ArrayList curPath = new ArrayList<>();
dfs(adjList, source, dest, visited, curPath, allPaths);
return allPaths;
}