您的位置:首页 > 财经 > 金融 > 运营管理_快速开发平台对比_百度灰色关键词代做_2023新一轮病毒叫什么名字

运营管理_快速开发平台对比_百度灰色关键词代做_2023新一轮病毒叫什么名字

2025/2/26 2:37:16 来源:https://blog.csdn.net/xiaoyixiaoyizhu/article/details/145503982  浏览:    关键词:运营管理_快速开发平台对比_百度灰色关键词代做_2023新一轮病毒叫什么名字
运营管理_快速开发平台对比_百度灰色关键词代做_2023新一轮病毒叫什么名字

Day56_20250204_图论part1_图论理论基础|深搜理论基础|98.所有可达路径|广搜理论基础

深搜理论基础

  • 基础知识

    • 深搜与广搜
    • 并查集
    • 最小生成树
    • 拓扑排序
    • 最短路算法
  • 图论理论基础

    • 图的基本概念

      • 多个点连线
    • 连通性

      • 表示节点的连通情况

      • 无向图

        • 连通图
        • 非连通图
        • 连通分量:极大连通子图。
      • 有向图

        • 强连通图
          • 任何两个节点是可以相互到达的。
        • 强连通分量:在有向图中极大强连通子图
    • 图的构造

      • 组成:邻接表、临接矩阵、类。主要是朴素存储、邻接表和临接矩阵
      • 邻接矩阵:
        • 二维数组来表示图结构。
        • 从节点的角度来表示图,有多少节点就申请多大的二维数组。
      • 邻接表
        • 数组+链表
        • 从边的数量来表示图,有多少边申请对应大小的链表。
    • 图的遍历方式

      • 深度优先搜索(dfs) ex:二叉树的递归遍历
      • 广度优先搜索(bfs) ex:二叉树的层序遍历

深度优先搜索理论基础(dfs)

  • dfs和bfs的区别

    • dfs深度优先搜索:

      • 可一个方向去搜,不到黄河不回头。直到无法继续搜下去,再换方向(回溯)
    • bfs广度优先搜索:

      • 先把本节点所连接的所有节点遍历一遍,走到下一个节点的时候,再把连接节点的所有节点遍历一遍,搜索方向更像是广度,四面八方的搜索过程。
  • dfs搜索过程

    • dfs搜索可一个方向,并需要回溯,所以用递归的方式来实现是最方便的。
  • 代码模板

    • dfs,回溯
      void dfs(参数){if(终止条件){存放结果;return;}for(选择:本节点所连接的其他节点){处理节点;dfs(图,选择的节点);回溯,撤销处理结果}}
      
  • 深搜三部曲

    void dfs(参数)//1.确认递归函数、参数
    //2.确认终止条件,收获结果
    if(终止条件){存放结果;return;
    }
    //3.处理目前搜索节点出发的路径
    for(选择:本节点所连接的其他节点){处理节点;dfs(图,选择的节点);//递归回溯,撤销处理结果
    }
    
    • 二维数组结构保存所有路径,一维数组保存单一路径。定义全局变量

      vector<vector<int>> result; // 保存符合条件的所有路径
      vector<int> path; // 起点到终点的路径
      void dfs (图,目前搜索的节点)  
      

98.所有可达路径

题目

给定一个有 n 个节点的有向无环图,节点编号从 1 到 n。请编写一个函数,找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。

输入:

第一行包含两个整数 N,M,表示图中拥有 N 个节点,M 条边

后续 M 行,每行包含两个整数 s 和 t,表示图中的 s 节点与 t 节点中有一条路径

输出:

输出所有的可达路径,路径中所有节点之间空格隔开,每条路径独占一行,存在多条路径,路径输出的顺序可任意。如果不存在任何一条路径,则输出 -1。

注意输出的序列中,最后一个节点后面没有空格! 例如正确的答案是 1 3 5,而不是 1 3 5 , 5后面没有空格!

例子:

输入:

5 5
1 3
3 5
1 2
2 4
4 5

输出:

输出所有的可达路径,路径中所有节点之间空格隔开,每条路径独占一行,存在多条路径,路径输出的顺序可任意。如果不存在任何一条路径,则输出 -1。

注意输出的序列中,最后一个节点后面没有空格! 例如正确的答案是 1 3 5,而不是 1 3 5 , 5后面没有空格!

思路

  • 思路
  • 代码
    • 邻接矩阵
      import java.util.ArrayList;//动态数组,存储任意类型的元素,
      import java.util.List;//有序的元素集合
      import java.util.Scanner;//从标准输入中读取数据
      public class Main{//2个路径static List<List<Integer>> result=new ArrayList<>();//所有路径static List<Integer> path=new ArrayList<>();//1节点到终点的路径public static void main(String[] args){//输入 n个节点,m条边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();//使用邻接矩阵表示无向图,1表示s与t是相连的graph[s][t]=1;}//路径搜索部分path.add(1);//无论什么路径已经是从1节点出发dfs(graph,1,n);//开始遍历//打印输出结果if(result.isEmpty()) System.out.println(-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));}}//递归public static void dfs(int[][] graph,int x,int n){//终止条件,当前遍历的节点x到达节点nif(x==n){result.add(new ArrayList<>(path));return;}for(int i=1;i<=n;i++){if(graph[x][i]==1){//找到x链接的节点path.add(i);//遍历到的节点加入到路径中来。dfs(graph,i,n);//下一层递归path.remove(path.size()-1);//回溯,撤销本节点}}}}
    • 邻接表
      import java.util.ArrayList;
      import java.util.LinkedList;
      import java.util.List;
      import java.util.Scanner;public class Main{//2个路径static List<List<Integer>> result=new ArrayList<>();//收集符合条件的路径static List<Integer> path=new ArrayList<>();//1节点到终点的路径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<>());}//?while(m-->0){int s=scanner.nextInt();int t=scanner.nextInt();//s和t是相连的graph.get(s).add(t);}path.add(1);//无论什么路径已经是从1节点出发dfs(graph,1,n);//开始遍历//打印输出结果if(result.isEmpty()) System.out.println(-1);//遍历并打印所有路径//遍历所有路径,pa每一条路径for(List<Integer> pa:result){//打印路径中的每个节点,从起点1到终点n的一条路径。最后输出一个多余的空格for(int i=0;i<pa.size()-1;i++){System.out.print(pa.get(i)+" ");}//打印路径最后一个节点System.out.println(pa.get(pa.size()-1));//}}public static void dfs(List<LinkedList<Integer>> graph,int x,int n){//终止条件if(x==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);//回溯,撤销本节点}}
      }
      

总结

  • 掌握邻接表和邻接图的代码写法
  • 挺复杂的,需要多练习几遍

广搜理论基础广搜(bfs)是一圈一圈的搜索过程,和深搜(dfs)是一条路跑到黑然后再回溯。

  • 使用场景:
    • 解决两个点之间的最短路径问题。
    • 广搜是从起点出发,以起始点为中心一圈一圈进行搜索,一旦遇到终点,记录之前走过的节点就是一条最短路。
    • 岛屿问题广搜深搜都可以,特征是不涉及具体的遍历方式,只要能把相邻且相同属性的节点标记上就行。
    • 外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
      • 一旦遇到终止点,一定是一条最短路径。地图中可以有障碍。
  • 怎么进行一圈一圈的搜索,放在什么容器里,才能这样去遍历。
    • 需要一个容器,保存遍历过的元素就可以。队列,栈,数组

      • 队列,每一圈都是一个方向去转,统一顺时针或逆时针
      • 栈,第一圈顺时针遍历,第二圈逆时针遍历,第三圈顺时针遍历
      • 数组,
    • int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
      // grid 是地图,也就是一个二维数组
      // visited标记访问过的节点,不要重复访问
      // x,y 表示开始搜索节点的下标
      void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {queue<pair<int, int>> que; // 定义队列que.push({x, y}); // 起始节点加入队列visited[x][y] = true; // 只要加入队列,立刻标记为访问过的节点while(!que.empty()) { // 开始遍历队列里的元素pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素int curx = cur.first;int cury = cur.second; // 当前节点坐标for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历int nextx = curx + dir[i][0];int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 坐标越界了,直接跳过if (!visited[nextx][nexty]) { // 如果节点没被访问过que.push({nextx, nexty});  // 队列添加该节点为下一轮要遍历的节点visited[nextx][nexty] = true; // 只要加入队列立刻标记,避免重复访问}}}}
      

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com