代码随想录算法训练营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.所有可达路径
题目
思路
图的存储：
-
邻接矩阵：
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<>();
// 起点为1
path.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<>();
// 起点为1
path.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. 所有可能的路径
题目
给你一个有 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.length2 <= n <= 150 <= graph[i][j] < ngraph[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; // 只要加入队列立刻标记，避免重复访问
}
}
}
}
原文地址：https://blog.csdn.net/jiabao0520/article/details/143593880
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！