代码随想录算法训练营 | 图论理论基础，98. 所有可达路径

图论理论基础
1.图的种类：有向图，无向图，加权有向图，加权无向图；2.度：无向图中有几条边连接该节点，该节点就有几度，在有向图中，每个节点有出度和入度；出度：从该节点出发的边的个数；入度：指向该节点边的个数；
3.连通图：在无向图中，任何两个节点都是可以到达的；强连通图：在有向图中，任何两个节点是可以相互到达的；
4.连通分量：在无向图中最大的联通子图；强连通分量：在有向图中极大强连通子图
5.图的构造：邻接表、邻接矩阵 或者用类来表示；
6.邻接矩阵：使用二维数组来表示图结构；邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组；
7.邻接表：使用数组 + 链表的方式来表示；邻接表是从边的数量来表示图，有多少边才会申请对应大小的链表。
8.dfs，bfs

98. 所有可达路径
题目链接：98. 所有可达路径
文档讲解︰代码随想录(programmercarl.com)
日期：2024-10-22

Java代码如下：

import java.util.*;

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.isEmpty()) System.out.print(-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));
        }
    }
}