力扣labuladong一刷day42天图的遍历
2023-12-20 14:34:41
力扣labuladong一刷day42天图的遍历
一、797. 所有可能的路径
题目链接:https://leetcode.cn/problems/all-paths-from-source-to-target/
思路:这是一个类似邻接表的形式,行索引为指向起始位置,元素值为被指向位置,图的遍历可以采用深度优先,利用有向进行跳转,跳转到尽头结束递归。当然递归必然伴随着回溯,不能光往list中收集元素,回溯返回时也要记得删除元素。
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> list = new ArrayList<>();
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
list.add(0);
traverse(graph, 0);
return result;
}
void traverse(int[][] graph, int deep) {
if (deep >= graph.length-1) {
result.add(new ArrayList<>(list));
return;
}
for (int i = 0; i < graph[deep].length; i++) {
int temp = graph[deep][i];
list.add(temp);
traverse(graph, temp);
list.remove(list.size()-1);
}
}
}
文章来源:https://blog.csdn.net/qq_43511039/article/details/135099995
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!