代码随想录算法训练营Day55 | 图论理论基础、深度优先搜索理论基础、卡玛网 98.所有可达路径、797. 所有可能的路径、广度优先搜索理论基础

图论理论基础

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

图的基本概念

图的种类

大体分为有向图和无向图。

图中的边有方向的是有向图：

图中的边没有方向的是无向图：

图中的边有权值的是加权图：

度

无向图中的节点的度数表示有几条边连接该节点。

如下图中节点4的度为5，节点6的度为3：

有向图中的节点有出度和入度，出度为从该节点出发的边的个数，入度为指向该节点的边的个数。

如下图中节点3的入度为2，出度为1，节点1的入度为0，出度为2：

连通性

连通性表示图中节点的连通情况。

连通图

无向图中，任何两个节点都可以到达的图叫做连通图 ：

如果有节点不能到达其它节点，则为非连通图：

强连通图

有向图中任何两个节点都可以相互到达的图叫做强连通图：

连通分量

无向图中的极大连通子图称之为该图的一个连通分量。

图中的节点1、2、5与节点3、4、6构成的两个子图就是该无向图中的两个连通分量，该子图所有节点都是相互可达到的。

强连通分量

有向图中的极大强连通子图称之为该图的强连通分量。

图中节点1、2、3、4、5构成的子图是强连通分量，节点6、7、8构成的子图不是强连通分量。

图的构造

邻接矩阵

邻接矩阵使用二维数组来表示图结构。邻接矩阵是从节点的角度来表示图，数组大小与节点数相同。

有向图：grid[2][5] = 6，表示节点 2 连接节点5 为有向图，节点2 指向节点5，边的权值为6。

无向图：grid[2][5] = 6, grid[5][2] = 6，表示节点2 与节点5 相互连通，权值为6。

如图：

优点：

表达方式简单，易于理解
检查任意两个节点间是否存在边的操作很快
适合稠密图，在边数接近顶点数平方的图中，邻接矩阵是一种空间效率较高的表示方法。

缺点：

遇到稀疏图，会导致申请过大的二维数组造成空间浪费，且遍历边的时候需要遍历整个 n * n 矩阵，造成时间浪费

邻接表

邻接表使用数组 + 链表的方式来表示图结构。邻接表是从边的数量来表示图，链表大小与边的数量相同。

节点1 指向节点3 和节点5
节点2 指向节点4、节点3、节点5
节点3 指向节点4
节点4指向节点1

优点：

对于稀疏图的存储，只需要存储边，空间利用率高
遍历节点连接情况相对容易

缺点：

检查任意两个节点间是否存在边，效率相对低，需要 O(V)时间，V表示某节点连接其他节点的数量。
实现相对复杂，不易理解

图的遍历

深度优先搜索（DFS）
广度优先搜索（BFS）

深度优先搜索理论基础

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

DFS 的关键是沿着一个方向搜索结果，直到无法继续搜索时再回溯换一个方向搜索。

代码框架：

void dfs(参数) {if (终止条件) {存放结果;return;}for (选择：本节点所连接的其他节点) {处理节点;dfs(图，选择的节点); // 递归回溯，撤销处理结果}
}

卡玛网 98.所有可达路径

题目

98. 所有可达路径

思路

代码随想录：98.所有可达路径

图的存储：

邻接矩阵：

        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 a = scanner.nextInt();int b = scanner.nextInt();graph[a][b] = 1;}

邻接表

        Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();int M = scanner.nextInt();List<LinkedList<Integer>> graph = new ArrayList<>(N + 1);for (int i = 0; i <= N; i++) {graph.add(new LinkedList<>());}for (int i = 0; i < M; i++) {int a = scanner.nextInt();int b = scanner.nextInt();graph.get(a).add(b);}

打印结果：

        //输出结果，注意最后一个数字不添加空格，但是要换行for (List<Integer> list : res) {for (int i = 0; i < list.size() - 1; i++) {System.out.print(list.get(i) + " ");}System.out.println(list.get(list.size() - 1));}

题解

邻接矩阵：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {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 a = scanner.nextInt();int b = scanner.nextInt();graph[a][b] = 1;}List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();// 起点为1path.add(1);dfs(res, path, graph, 1);if (res.isEmpty())System.out.println(-1);//输出结果，注意最后一个数字不添加空格，但是要换行for (List<Integer> list : res) {for (int i = 0; i < list.size() - 1; i++) {System.out.print(list.get(i) + " ");}System.out.println(list.get(list.size() - 1));}}static void dfs(List<List<Integer>> res, List<Integer> path, int[][] graph, int index) {if (index == graph.length - 1) {res.add(new ArrayList<>(path));return;}for (int i = 1; i < graph.length; i++) {if (graph[index][i] == 1) {path.add(i);dfs(res, path, graph, i);path.remove(path.size() - 1);}}}
}

邻接表：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();int M = scanner.nextInt();// 下标与题目输入保持一致List<LinkedList<Integer>> graph = new ArrayList<>(N + 1);// 初始化邻接表for (int i = 0; i <= N; i++) {graph.add(new LinkedList<>());}for (int i = 0; i < M; i++) {int a = scanner.nextInt();int b = scanner.nextInt();graph.get(a).add(b);}List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();// 起点为1path.add(1);dfs(res, path, graph, 1);if (res.isEmpty())System.out.println(-1);//输出结果，注意最后一个数字不添加空格，但是要换行for (List<Integer> list : res) {for (int i = 0; i < list.size() - 1; i++) {System.out.print(list.get(i) + " ");}System.out.println(list.get(list.size() - 1));}}static void dfs(List<List<Integer>> res, List<Integer> path, List<LinkedList<Integer>> graph, int index) {if (index == graph.size() - 1) {res.add(new ArrayList<>(path));return;}for (int i : graph.get(index)) {path.add(i);dfs(res, path, graph, i);path.remove(path.size() - 1);}}
}

797. 所有可能的路径

题目

797. 所有可能的路径 - 力扣（LeetCode）

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

示例 1：

在这里插入图片描述

输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

示例 2：

在这里插入图片描述

输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

提示：

n == graph.length
2 <= n <= 15
0 <= graph[i][j] < n
graph[i][j] != i（即不存在自环）
graph[i] 中的所有元素 互不相同
保证输入为 有向无环图（DAG）

思路

在遍历之前先将 0 号几点加入路径。

由于本题的图为有向无环图（DAG），搜索过程中不会反复遍历同一个点，所以无需判断当前点是否遍历过。

题解

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> allPathsSourceTarget(int[][] graph) {path.add(0);dfs(graph, 0);return res;}void dfs(int[][] graph, int index) {if (index == graph.length - 1) {res.add(new ArrayList<>(path));return;}for (int neighbor : graph[index]) {path.add(neighbor);dfs(graph, neighbor);path.remove(path.size() - 1);}}
}

广度优先搜索理论基础

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

BFS 是从起点开始一圈一圈进行搜索的过程，如图：

选择使用队列作为容器。

模板代码：

    // 表示四个方向，分别是右、下、左、上private static final int[][] DIR = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};// grid 是地图，也就是一个二维数组// visited 标记访问过的节点，不要重复访问// x, y 表示开始搜索节点的下标public static void bfs(char[][] grid, boolean[][] visited, int x, int y) {Queue<int[]> queue = new LinkedList<>(); // 定义队列queue.add(new int[]{x, y}); // 起始节点加入队列visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点while (!queue.isEmpty()) { // 开始遍历队列里的元素int[] cur = queue.poll(); // 从队列取元素int curx = cur[0];int cury = cur[1]; // 当前节点坐标for (int i = 0; i < 4; i++) { // 开始向当前节点的四个方向（左右上下）遍历int nextx = curx + DIR[i][0];int nexty = cury + DIR[i][1]; // 获取周边四个方向的坐标// 坐标越界了，直接跳过if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) {continue;}if (!visited[nextx][nexty]) { // 如果节点没被访问过queue.add(new int[]{nextx, nexty}); // 队列添加该节点为下一轮要遍历的节点visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问}}}}