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

图论篇--代码随想录算法训练营第五十天打卡| 深度优先搜索理论基础,98. 所有可达路径,广度优先搜索理论基础

深度优先搜索理论基础

DFS模板:

void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择:本节点所连接的其他节点) {
        处理节点;
        dfs(图,选择的节点); // 递归
        回溯,撤销处理结果
    }
}

98. 所有可达路径

题目链接:98. 所有可达路径

题目描述:

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

解题思路:

该题目是深度优先搜索的一个简单应用。本题的关键是

  1. 熟悉深搜模板
  2. 存储方式--本题采用邻接表存储,如下图所示。

 

代码:

#include<iostream>
#include<vector>
#include<list>
using namespace std;

vector<int> path;
vector<vector<int>> result;

void dfs(vector<list<int>>& nodes, int start, int end)
{
    if(start == end) 
    {
        result.push_back(path);
        return;
    }
    for(auto node : nodes[start])
    {
        path.push_back(node);
        dfs(nodes,node,end);
        path.pop_back();
    }
    
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<list<int>> nodes(n+1);
    for(int i = 0; i < m; i++)
    {
        int s,t;
        cin >> s >> t;
        nodes[s].push_back(t);
    }
    path.push_back(1);
    dfs(nodes,1,n);
    if(result.empty()) cout << "-1" << endl;
    for(auto v: result)
    {
        
        for(int i = 0; i < v.size()-1; i++)
            cout << v[i] << " ";
        cout << v[v.size()-1] << endl;

    }
    return 0;
}

广度优先搜索理论基础

原理讲解:

用一个方格地图,假如每次搜索的方向为 上下左右(不包含斜上方),那么给出一个start起始位

置,那么BFS就是从四个方向走出第一步。

代码实现中,只要能找到一个能保存我们要遍历过的元素的容器就可以。此处可以选择队列

由于广搜不考虑转圈搜索的顺序,因此当前栈和队列使用时没有区别。

BFS模板: 

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

}


http://www.kler.cn/news/295043.html

相关文章:

  • 数字化转型专家讲师培训师唐兴通中欧国际工商学院数字化转型战略与实现路径AIGC人工智能数字化战略数字商业模式创新
  • 【数据库中级】1_DBeaver操作数据库
  • 【微信小程序】搭建项目步骤 + 引入Tdesign UI
  • Flink SQL 中常见的数据类型
  • 开源网安引领AIGC+开发安全,智能防护铸就软件安全新高度
  • 【Springboot基础知识】
  • 基于 rt-thread的I2C操作EEPROM(AT24C02)
  • 如何在mac上玩使命召唤手游?苹果电脑好玩的第一人称射击游戏推荐
  • 【linux学习指南】Linux编译器 gcc和g++使用
  • python 中使用tkinter构建一个图片的剪切器-附源码
  • 漫谈设计模式 [15]:观察者模式
  • 9. 相机控件OrbitControls
  • C++11线程池、多线程编程(附源码)
  • 信息熵|atttion矩阵的注意力熵
  • 设计并用Java实现一个简易的规则引擎
  • Python | Leetcode Python题解之第392题判断子序列
  • 【leetcode详解】爬楼梯:DP入门典例(附DP通用思路 同类进阶练习)
  • 使用Protocol Buffers传输数据
  • 在vscode中用virtual env的方法
  • git如何灵活切换本地账号对应远程github的两个账号
  • 代码随想录:279. 完全平方数
  • 如何在Selenium中使用Chrome进行网络限速
  • ComfyUI+Krea免费利用AI制作网站萌宠IP,五步搞定制作AI萌宠
  • React 响应事件
  • 【Godot4.3】多边形的斜线填充效果基础实现
  • 在Ubuntu 20.04上安装Nginx的方法
  • 懒人笔记-opencv4.8.0篇
  • 【详解 Java 注解】
  • 一些数学经验总结——关于将原一元二次函数增加一些限制条件后最优结果的对比(主要针对公平关切相关的建模)
  • 分数阶微积分MATLAB计算