DFS，BFS最短路，树与图的深度/广度优先遍历，拓扑排序

DFS

例题：排列数字
在排列组合问题中，每个位置需要尝试多个不同的数字组合，需要回溯以尝试不同的可能性。因此，需要显式地恢复现场（撤销标记），以确保每个可能的路径都被探索。

#include <bits/stdc++.h>
using namespace std;

const int N = 10;
int path[N];
bool st[N];
int n;

void dfs(int u)
{
    if (u == n)
    {
        for (int i = 0; i < n; i++) printf("%d ", path[i]);
        puts("");
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (!st[i])
        {
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            st[i] = false; //还原
        }
    }
}

int main()
{
    scanf("%d", &n);
    dfs(0);
    return 0;
}

例题：n-皇后问题
按位置枚举，复杂度较高：

#include <bits/stdc++.h>
using namespace std;

const int N = 10;
char g[N][N];
bool row[N], col[N], dg[N * 2], udg[N * 2];
int n;

void dfs(int x, int y, int s)
{
    if (y == n)
    {
        y = 0;
        x++;
    }
    if (x == n)
    {
        if (s == n)
        {
            for (int i = 0; i < n; i++) printf("%s\n", g[i]);
            puts("");
        }
        return; //记得return
    }
    
    //不放
    dfs(x, y + 1, s);
    
    //放
    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
    {
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        dfs(x, y + 1, s + 1);
        g[x][y] = '.';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++) g[i][j] = '.';
    }
    dfs(0, 0, 0);
    return 0;
}

BFS

当所有路权值为1时，求最短路用bfs。

例题：走迷宫
以下是加上打印路径后的代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
typedef pair<int, int> PII;
int g[N][N], d[N][N];
vector<PII> path;
PII pre[N][N];
int n, m;
int dx[4] = {0, 0, 1, -1}, dy[4] = {-1, 1, 0, 0};

int bfs(int x, int y)
{
    queue<PII> q;
    q.push({x, y});
    memset(d, -1, sizeof d);
    memset(pre, -1, sizeof pre);
    d[x][y] = 0;
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int tx = t.first + dx[i], ty = t.second + dy[i];
            if (tx < 0 || ty < 0 || tx >= n || ty >= m) continue;
            if (g[tx][ty] == 1 || d[tx][ty] != -1) continue;
            d[tx][ty] = d[t.first][t.second] + 1;
            pre[tx][ty] = {t.first, t.second};
            q.push({tx, ty});
        }
    }
    return d[n - 1][m - 1];
}

void getpath()
{
    if (d[n - 1][m - 1] == -1) return;
    for (PII at = {n - 1, m - 1}; at != make_pair(-1, -1); at = pre[at.first][at.second])
    {
        path.push_back(at);
    }
    reverse(path.begin(), path.end());
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)  cin >> g[i][j];
    }
    printf("The shortest path length: %d\n", bfs(0, 0));
    getpath();
    if (path.empty()) printf("No path found.");
    else
    {
        printf("path: ");
        for (auto p: path)
        {
            printf("(%d, %d) ", p.first, p.second);
        }
    }
}

例题：八数码

#include <bits/stdc++.h>
using namespace std;

char c;
string start;

int bfs(string start)
{
    string end = "12345678x";
    queue<string> q;
    unordered_map<string, int> d; //距离
    q.push(start);
    d[start] = 0;
    
    //转移方式，可以从上下左右转移到x
    int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        int distance = d[t];
        if (t == end) return distance;
        
        //查询x在字符串中的下标，转换成二维坐标
        int k = t.find('x');
        int x = k / 3, y = k % 3;
        
        for (int i = 0; i < 4; i++)
        {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx >= 0 && tx < 3 && ty >= 0 && ty < 3)
            {
                //转移x
                swap(t[k], t[tx * 3 + ty]);
                
                //如果之前没有遍历过这种状态
                //count方法可以用来检查某个键是否存在，返回键在unordered_map中出现的次数
                //（对于unordered_map来说，这个值要么是0，要么是1，因为键是唯一的）。
                if (!d.count(t))
                {
                    d[t] = distance + 1;
                    q.push(t);
                }
                
                //还原状态
                swap(t[k], t[tx * 3 + ty]);
                //假设我们在某个状态"12345678x"，x的位置在右下角。
                //第一次交换x和左边的数字生成状态"1234567x8"。
                //如果不还原状态，结果就是基于状态"1234567x8"而不是"12345678x"进行的，这显然是错误的。
            }
        }
    }
    return -1;
}

int main()
{
    for (int i = 0; i < 9; i++)
    {
        //过滤空格并存储到字符串中
        cin >> c;
        start += c;
    }
    printf("%d", bfs(start));
    return 0;
}

树与图的深度优先遍历

树与图的深度优先遍历每个节点只遍历一次，用dfs不用恢复现场。
用邻接表存储。这题是无向图。
例题：树的重心

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10, M = N * 2;
int n;
//h存储每个节点的头指针，e存储边的终点，ne存储下一条边的索引，idx为当前边的索引
//由于每条无向边需要存储两次，因此如果有 m 条边，需要分配 2 * m 的空间给 e[] 和 ne[] 数组
int h[N], e[M], ne[M], idx; //树或图邻接表中的idx用作每条边的唯一索引
int ans = N; //用于存储当前重心的最大子树大小的最小值
bool st[N];

void add(int a, int b)
{
    e[idx] = b; //记录边的终点
    ne[idx] = h[a]; //将当前边的索引插入到邻接表头部。
    h[a] = idx; //更新邻接表头指针，使其指向新插入的边。
    idx++;
}

int dfs(int u)
{
    st[u] = true;
    //size用于存储以u为根节点的树的子树（即连通图，不包含u）的最大大小，sum用于存储以u为根节点的树的节点总和
    int size = 0, sum = 1;
    // 遍历节点u的所有邻接边
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (st[j]) continue;
        int s = dfs(j); // 递归计算子树的大小
        size = max(size, s);
        sum += s;
    }
    
    //st数组标记是否被遍历，又因为main函数里dfs（1）这个1是随意的，
    //如果从1开始，我们知道4是树的重心，而这时候遍历4的时候，因为1已经被遍历过了，
    //所以size在for循环里不能往上走（不能往1那边走），n - sum表示另一边已经被遍历过的连通块节点数，
    //那res = max(res, n - sum);就能够计算将重心删除后，剩余各个连通块中点数的最大值。
    size = max(size, n - sum);
    ans = min(size, ans); //遍历过的假设重心中，最小的 最大联通子图的节点数
    return sum;
}

int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h); // 初始化头指针数组为-1，表示没有边
    for (int i = 0; i < n - 1; i++) // 读取n-1条边（树有n个节点，n-1条边）
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    dfs(1);
    printf("%d", ans);
    return 0;
}

树的广度优先遍历

例题：图中点的层次
这题是有向图。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

int bfs()
{
    memset(d, -1, sizeof d);
    queue<int> q;
    d[1] = 0;
    q.push(1);
    while (q.size())
    {
        int t = q.front();
        q.pop();
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i]; //节点编号
            if (d[j] == -1)
            {
                q.push(j);
                d[j] = d[t] + 1;
            }
        }
    }
    return d[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }
    printf("%d", bfs());
    return 0;
}

拓扑排序

有向图才有拓扑序列。存在环一定没有拓扑序列。
有向无环图一定存在拓扑序列，一定至少存在一个入度为0的点，也被称为拓扑图。
例题：有向图的拓扑排序

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int d[N]; //每个点的入度
int n, m;

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
    d[b]++; //b的入度加1
}

void topsort()
{
    queue<int> q;
    vector<int> ans;
    for (int i = 1; i <= n; i++)
    {
        if (d[i] == 0) q.push(i); //入度为0节点的入列，可以作为拓扑序列的第一个
    }
    while (q.size())
    {
        int t = q.front();
        ans.push_back(t); // 用于保存拓扑排序结果
        q.pop();
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i]; //节点的编号
            d[j]--; //删除出队的结点指向这个点的边，这个点的入度-1
            if (d[j] == 0)
            {
                q.push(j);
            }
        }
    }
    if (ans.size() == n) // 如果队列中的点的个数与图中点的个数相同，则可以进行拓扑排序
    {
        for (int i = 0; i < n; i++) printf("%d ", ans[i]);
    }
    else
    {
        printf("-1");
    }
}



int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }
    topsort();
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/770922.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

git常用命令速查表

git常用命令速查表

Git相关概念简述 版本库&#xff1a;git在本地开辟的一个存储空间&#xff0c;一般在 .git 文件里。工作区(workspace)&#xff1a; 就是编辑器里面的代码&#xff0c;我们平常开发直接操作的就是工作区。暂存区&#xff08;index/stage&#xff09;&#xff1a;暂时存放文件的…
阅读更多...
java设计模式（十二）享元模式（Flyweight Pattern）

java设计模式（十二）享元模式（Flyweight Pattern）

1、模式介绍&#xff1a; 享元模式是一种结构型设计模式&#xff0c;旨在通过共享对象来有效支持大量细粒度的对象。它通过将对象的状态分为内部状态&#xff08;可共享&#xff09;和外部状态&#xff08;不可共享&#xff09;来减少内存消耗和提高性能。内部状态存储在享元对…
阅读更多...
webstorm 高效查看不同分支差异 摒弃你的git diff手动操作

webstorm 高效查看不同分支差异 摒弃你的git diff手动操作

背景 每次代码冲突或者版本发生异常时&#xff0c;排查不同版本时就是一个头大的问题&#xff0c;头大的点在于用 vscode 的 git diff 一点点地排查和比较&#xff0c;耗时耗力&#xff0c;版面展不开&#xff0c;commit 差异看不出来&#xff0c;每个页面的代码不同也不能快速…
阅读更多...
为本地化准备营销材料的几个步骤

为本地化准备营销材料的几个步骤

为本地化准备营销材料涉及几个关键步骤&#xff0c;以确保内容在文化上合适、语言上准确&#xff0c;并与目标受众相关。以下是五个基本步骤&#xff1a; 进行市场调查 了解目标市场至关重要。进行深入研究&#xff0c;以收集有关目标地区受众的文化细微差别、消费者行为、地…
阅读更多...
一键安装部署，在 Ubuntu 服务器上快速搭建基于 Ghost CMS的网站

一键安装部署，在 Ubuntu 服务器上快速搭建基于 Ghost CMS的网站

我们在上一篇内容中讲过&#xff0c;如何使用 Helm 在 Kubernetes 集群上安装 WordPress&#xff0c;创建高可用性网站。而这次我们将基于另一个流行的内容管理系统 Ghost CMS 在 DigitalOcean 云主机进行建站。 Ghost 也是开源的内容管理系统&#xff08;CMS&#xff09;&…
阅读更多...
权限控制权限控制权限控制权限控制权限控制

权限控制权限控制权限控制权限控制权限控制

1.权限的分类 视频学习&#xff1a;https://www.bilibili.com/video/BV15Q4y1K79c/?spm_id_from333.337.search-card.all.click&vd_source386b4f5aae076490e1ad9b863a467f37 1.1 后端权限 1. 后端如何知道该请求是哪个用户发过来的 可以根据 cookie、session、token&a…
阅读更多...
昇思25天学习打卡营第15天 | Vision Transformer图像分类

昇思25天学习打卡营第15天 | Vision Transformer图像分类

内容介绍&#xff1a; 近些年&#xff0c;随着基于自注意&#xff08;Self-Attention&#xff09;结构的模型的发展&#xff0c;特别是Transformer模型的提出&#xff0c;极大地促进了自然语言处理模型的发展。由于Transformers的计算效率和可扩展性&#xff0c;它已经能够训练…
阅读更多...
【机器学习】机器学习与图像识别的融合应用与性能优化新探索

【机器学习】机器学习与图像识别的融合应用与性能优化新探索

文章目录 引言第一章&#xff1a;机器学习在图像识别中的应用1.1 数据预处理1.1.1 数据清洗1.1.2 数据归一化1.1.3 数据增强 1.2 模型选择1.2.1 卷积神经网络1.2.2 迁移学习1.2.3 混合模型 1.3 模型训练1.3.1 梯度下降1.3.2 随机梯度下降1.3.3 Adam优化器 1.4 模型评估与性能优…
阅读更多...
Docker镜像加速配置

Docker镜像加速配置

由于当前运营商网络问题&#xff0c;可能会导致您拉取 Docker Hub 镜像变慢&#xff0c;索引可以配置阿里云镜像加速器。阿里云登录 - 欢迎登录阿里云&#xff0c;安全稳定的云计算服务平台 每个人镜像地址都不一样&#xff0c;需要登陆阿里云自行查看&#xff0c;地址在上面&a…
阅读更多...
ctfshow-web入门-文件包含（web78、web79、web80、web81）

ctfshow-web入门-文件包含（web78、web79、web80、web81）

目录 1、web78 2、web79 3、web80 4、web81 1、web78 存在文件包含函数&#xff1a;include 直接上 php 伪协议&#xff0c;用 php://filter 读文件&#xff08;flag.php&#xff09;的源码&#xff0c;payload&#xff1a; ?filephp://filter/readconvert.base64-encode…
阅读更多...
轻松实现百度大模型ERNIE对话

轻松实现百度大模型ERNIE对话

该代码直接可用&#xff0c;实现了流式输出&#xff0c;只需要在你自己的开发环境配置百度申请的QIANFAN_AK和QIANFAN_SK即可使用啦。// # 在.env文件中&#xff0c;设置以下内容&#xff0c;安全认证Access Key替换your_iam_ak&#xff0c;Secret Key替换your_iam_sk 不过需要…
阅读更多...
Linux Ubuntu 将指定ip添加到DNS

Linux Ubuntu 将指定ip添加到DNS

请严格按照如下步骤操作 以ip地址&#xff1a;202.96.134.133 为例 1.修改 /etc/resolv.conf 文件 sudo gedit /etc/resolv.conf 添加 nameserver 8.8.8.8 和 nameserver 202.96.134.133&#xff0c; 如下图方框指定内容&#xff1a; 2.修改 /etc/resolvconf/resolv.conf.d…
阅读更多...
Python28-7.1降维算法之LDA线性判别分析

Python28-7.1降维算法之LDA线性判别分析

线性判别分析&#xff08;Linear Discriminant Analysis, LDA&#xff09;是一种用于模式识别和机器学习的分类和降维技术。LDA通过找到能最大化类别间方差和最小化类别内方差的投影方向&#xff0c;实现样本的降维和分类。 LDA的基本思想 LDA的核心思想是通过线性变换将数据…
阅读更多...
Docker学习笔记（一）概念理解

Docker学习笔记（一）概念理解

一、什么是docker容器 Docker容器是一种轻量级、可移植的软件封装技术&#xff0c;它允许开发者将应用程序及其依赖、配置文件、运行环境等打包到一个独立的、自包含的执行单元中。容器与虚拟机相似&#xff0c;都提供了隔离的运行环境&#xff0c;但容器更加轻量级&#xff0c…
阅读更多...
Echarts折线+柱状图的多y轴

Echarts折线+柱状图的多y轴

实现效果&#xff1a; 代码&#xff1a; <template><div class"test-echart"><div id"barLineChart" ref"barLineChart" :style"barLineStyle"></div></div> </template> <script> // imp…
阅读更多...
MySQL之MHA高可用集群及故障切换

MySQL之MHA高可用集群及故障切换

一、MHA概述 MHA&#xff08;MasterHigh Availability&#xff09;是一套优秀的mysql高可用环境下故障切换和主从复制的软件。MHA的出现就是为了解决mysql单点故障。Mysql故障切换过程中&#xff0c;MHA能做到0-30秒内自动完成故障性切换操作。MHA能在故障切换的过程中最大程度…
阅读更多...
【路由交换技术】Cisco Packet Tracer基础入门教程（五）

【路由交换技术】Cisco Packet Tracer基础入门教程（五）

这一期我们来学习端口聚合&#xff0c;这是针对交换机的技术 前言 不知道大家有没有注意到&#xff0c;我们之前的实验在交换机与交换机之间只用一条线连接&#xff0c;像这样 通过今天的学习&#xff0c;我们要用两条线来连接交换机&#xff0c;就像这样&#xff08;为了能…
阅读更多...
3D问界—法线空间与应用举例

3D问界—法线空间与应用举例

问题提出&#xff1a;什么是法线空间&#xff0c;有哪些应用的场景&#xff1f; 法线空间&#xff08;Normal Space&#xff09;在计算机图形学中是一个重要的概念&#xff0c;特别是在处理表面法线&#xff08;Normal&#xff09;时常被提及。 1. 法线空间的分类 法线空间是相…
阅读更多...
“工控机”是什么？和普通电脑有区别嘛！

“工控机”是什么？和普通电脑有区别嘛！

在现代工业生产中，有一种特殊的计算机，它不像普通电脑那样被放置于明亮的办公室内，而是常常藏身于机器轰鸣、环境恶劣的工厂车间里，这就是工控机——工业控制计算机的简称。作为工业自动化领域不可或缺的核心设备，工控机不仅承载着监控与数据采集（SCADA）、过程控制、数据…
阅读更多...
python 实现docx指定语言翻译(不丢失格式)

python 实现docx指定语言翻译(不丢失格式)

我这边有个需求需要把一份docx翻译成指定语言的文档并且保存&#xff0c;研究了下&#xff0c;记录。 首先先安装依赖 pip install python-docx1.1.2 googletrans4.0.0rc1 python-docx是用来读取docx的&#xff0c;googletrans使用来翻译的。 googletrans PyPI 这个是官方文…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站