当前位置： 首页 > article >正文

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

article 2024/11/9 4:23:34

目录

图论理论基础

深度优先搜索理论基础

卡玛网 98.所有可达路径

广度优先搜索理论基础

图论理论基础

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

图的基本概念

图的种类

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

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

img

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

img

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

img

度

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

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

img

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

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

img

连通性

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

连通图

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

img

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

img

强连通图

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

img

连通分量

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

img

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

强连通分量

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

img

图中节点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。

如图：

img

优点：

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

缺点：

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

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

img

  • 节点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.所有可达路径

图的存储：

  1. 邻接矩阵：

            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;
        }

  2. 邻接表

            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. 所有可能的路径

题目

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; // 只要加入队列立刻标记，避免重复访问
                }
            }
        }
    }

http://www.kler.cn/a/385326.html

相关文章：

  • 智能提醒助理系列-jdk8升级到21，springboot2.3升级到3.3
  • java-web-web后端知识小结
  • LangChain实际应用
  • 深度洞察| 超6亿银发精准流量，40+泛银发群体参与消费三大变化
  • 2024软件测试面试热点问题
  • 【C/C++】strncpy函数的模拟实现
  • 一级注册消防工程师重点笔记
  • ICT网络赛道安全考点知识总结4
  • SearchGPT 网络搜索功能利用了微软必应的搜索技术
  • 2024网鼎杯web1+re2 wp
  • O-RAN前传Spilt Option 7-2x
  • RPA是什么，RPA有什么作用？
  • 如何在 Docker 容器中启动 X11 图形界面程序
  • 前端UniApp面试题及参考答案（100道题）
  • C++ enable_shared_from_this使用详解
  • 函数基础练习（Python）
  • 少儿编程启蒙学习
  • python爬虫指南——初学者避坑篇
  • leetcode | 88. 合并两个有序数组
  • WebSocket 及时通信 - 2024最新版前端秋招面试短期突击面试题【100道】
  • 远程控制项目第二天
  • 【GPTs】Email Responder Pro：高效生成专业回复邮件
  • mysql分布式锁
  • CSS实现图片3D立体效果
  • 苍穹外卖学习记录
  • OkHttp网络请求框架