代码随想录算法训练营第五四天| 图论理论基础 深度优先搜索理论基础 98. 所有可达路径 广度优先搜索理论基础
今日任务
图论理论基础
深度优先搜索理论基础
98. 所有可达路径
广度优先搜索理论基础
98. 所有可达路径
题目链接: 98. 所有可达路径
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* @author z00598929
* @date 2024/10/8 17:10
*/
public class Main {
static List<List<Integer>> result = new ArrayList<>();
static List<Integer> path = new ArrayList<>();
public static void dfs(int[][] graph, int x, int n) {
if (x == n) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 1; i <= n; i++) {
if (graph[x][i] == 1) {
path.add(i);
dfs(graph, i, n);
path.remove(path.size() - 1);
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] graph = new int[n + 1][n + 1];
for (int i = 0; i < m; i++) {
int s = scanner.nextInt();
int t = scanner.nextInt();
graph[s][t] = 1;
}
path.add(1);
dfs(graph, 1, n);
/* 输出结果 */
if (result.size() == 0) System.out.println("-1");
for(List<Integer> pa : result) {
for (int i = 0; i < pa.size() - 1; i++) {
System.out.print(pa.get(i) + " ");
}
System.out.println(pa.get(pa.size() - 1));
}
}
}
797.所有可达路径
题目连接: . - 力扣(LeetCode)
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
path.add(0);
dfs(graph, 0);
return result;
}
public void dfs(int[][] graph, int x){
if (x == graph.length - 1) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < graph[x].length; i++) {
if (graph[x][i] != 0) {
path.add(graph[x][i]);
dfs(graph, graph[x][i]);
path.remove(path.size() - 1);
}
}
return;
}
}
原文地址:https://blog.csdn.net/zzhnwpu/article/details/142773719
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!