图论理论基础
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));}}
}
