Day50 图论part01

图论理论基础

大家可以在看图论理论基础的时候，很多内容看不懂，例如也不知道看完之后还是不知道邻接矩阵，邻接表怎么用，别着急。

理论基础大家先对各个概念有个印象就好，后面在刷题的过程中，每个知识点都会得到巩固。

图论理论基础 | 代码随想录

深搜理论基础

了解一下深搜的原理和过程

深度优先搜索理论基础 | 代码随想录

98. 所有可达路径

代码随想录

方法1：邻接矩阵

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;public class Main{public static List<Integer> path = new ArrayList<>();public static List<List<Integer>> result = new ArrayList<>();public static void main (String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[][] graph = new int[n+1][n+1];while(m-- > 0){int s = sc.nextInt();int t = sc.nextInt();graph[s][t] = 1;}path.add(1);dfs(graph, 1, n);if(result.isEmpty()){System.out.println(-1);}for(List<Integer> p : result){for(int i = 0; i < p.size() - 1; i++){System.out.print(p.get(i) + " ");}System.out.println(p.get(p.size() - 1));}}public static void dfs(int[][] graph, int x, int n){//这里n是表示节点数量if(x == n){//这里的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);}}}}

方法2：邻接链表

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;public class Main{public static List<Integer> path = new ArrayList<>();public static List<List<Integer>> result = new ArrayList<>();public static void main (String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();List<LinkedList<Integer>> graph = new ArrayList<>(n+1);for(int i = 0; i <= n; i++){graph.add(new LinkedList<>());}while(m-- > 0){int s = sc.nextInt();int t = sc.nextInt();graph.get(s).add(t);}path.add(1);dfs(graph, 1, n);if(result.isEmpty()){System.out.println(-1);}for(List<Integer> p : result){for(int i = 0; i < p.size() - 1; i++){System.out.print(p.get(i) + " ");}System.out.println(p.get(p.size() - 1));}}public static void dfs(List<LinkedList<Integer>> graph, int x, int n){//这里n是表示节点数量if(x == n){//这里的n是表示路径的终节点result.add(new ArrayList<>(path));return;}for(int i : graph.get(x)){path.add(i);dfs(graph, i, n);path.remove(path.size() - 1);}}}

总结：

1.本题练习的是ACM模式，所以必须熟悉图的存储方法和结果的输出方法。图的存储方法分为邻接矩阵和邻接链表。邻接矩阵是从节点的角度来表示图，使用二维数组来表示图结构。例如： grid[2][5] = 6，表示节点 2 连接节点5 为有向图，节点2 指向节点5，边的权值为6。如果想表示无向图，即：grid[2][5] = 6，grid[5][2] = 6，表示节点2 与节点5 相互连通，权值为6。邻接链表一般是通过数组+链表，数组里面就存放节点，链表里面存放的是节点可以连通的节点，也就是边。比如1-3-5 表示的是节点1 指向节点3 和节点5，并不是节点1连着3，3后面连着5，这点要搞清楚。链表一般是通过这种方法创建的List<LinkedList<Integer>> graph = new ArrayList<>(n+1);然后记得LinkedList<Integer>一定要先new 出来，然后在add元素进去。

2.dfs里面的处理逻辑就比较简单了，我们先找到当前节点连通的节点 path.add(i);然后以该连通的节点递归继续就行查找dfs(graph, i, n);直到找到目标节点，然后回溯 path.remove(path.size() - 1);

3.由于题目中说了图中不存在自环，所以起始节点不会被自动加入到路径里面，需要我们手动加入到路径当中。