搜索与图论(一)(深搜,广搜,树与图的存储遍历,拓扑排序)

一、DFS

往深里搜,搜到叶子结点那里,回溯,到可以继续到叶子结点深搜的位置。

1、回溯一定要恢复现场

2、定义一个与当前递归层数有关的终止条件(题目要求的东西)

3、每层都用循环判断是否存在可以dfs的路

输出数字组合

#include<bits/stdc++.h>
//842排列数字 按照字典序将n个数
using namespace std;
const int N=1e5+10;
int path[N];//记录走过的路径
int st[N];//用来记录某个元素是否被用过
int n;
void dfs(int u)
{
    //先判断是否已经得到一个答案
    if(u==n)
    {
        for(int i=0;i<n;i++)cout<<path[i]<<" ";
        puts("");
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!st[i])//剪枝的过程找到可以构成dfs路径的方向
        {
            st[i]=true;
            path[u]=i;
            dfs(u+1);
            path[i]=0;//恢复现场
            st[i]=false;
        }
    }
}
int main()
{
       cin>>n;
       dfs(0);
       return 0;
}

全排列的思想解决n皇后问题,用三个bool数组描述限制条件,用二维char数组保存结果,在恢复现场的时候也要恢复g数组,因为后面的其他结果可能不会将其覆盖掉。

#include<bits/stdc++.h>
//843 n皇后问题(全排列问题)
using namespace std;
const int N=20;
int path[N];//记录走过的路径
char g[N][N];
bool col[N],row[N],dg[N],udg[N];
int n;
void dfs(int u)
{
    //先判断是否已经得到一个答案
    if(u==n)
    {
        for(int i=0;i<n;i++)puts(g[i]);
        puts("");
        return;
    }
    for(int i=0;i<n;i++)
    {
       if(!col[i]&&!dg[u+i]&&!udg[n-u+i])
       {
           g[u][i]='Q';
           col[i]=dg[u+i]=udg[n-u+i]=true;
           dfs(u+1);
           col[i]=dg[u+i]=udg[n-u+i]=false;
           g[u][i]='.';
       }
    }
}
int main()
{
       cin>>n;
       for(int i=0;i<n;i++)
          for(int j=0;j<n;j++)
             g[i][j]='.';

       dfs(0);
       return 0;
}

 按照元素枚举的方式解决n皇后问题

#include<bits/stdc++.h>
//843 n皇后问题(全排列问题)
using namespace std;
const int N=20;
int path[N];//记录走过的路径
char g[N][N];
bool col[N],row[N],dg[N],udg[N];
int n;
void dfs(int x,int y,int u)//x为行,y为列
{
    if(y==n)y=0,x++;
    if(x==n)
    {
        if(u==n)//有可能到头了也没有找到全部的皇后
        {
            for(int i=0; i<n; i++)puts(g[i]);
            puts("");
        }
        return;
    }

    //为什么要添加xy两个参数
    //因为这个思路不是循环式地剪枝,是利用递归进行搜索
    //处理坐标

    //不放当前位置
    dfs(x,y+1,u);
    //放当前位置
    if(!row[x]&&!col[y]&&!dg[x+y]&&!udg[n-y+x])
    {
        g[x][y]='Q';
        row[x]=col[y]=dg[x+y]=udg[n-y+x]=true;
        dfs(x,y+1,u+1);
        g[x][y]='.';
        row[x]=col[y]=dg[x+y]=udg[n-y+x]=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第一次搜到的点具有最短路性质

1、具有最短路性质的原因:因为bfs每次都向外扩展一层,依次找到距离起点为1,2,3的所有点。

#include<bits/stdc++.h>
//844走迷宫//添加路径
using namespace std;
const int N=110;
typedef pair<int,int>PII;
int g[N][N];//存图
int d[N][N];//存距离
PII q[N*N];//模拟队列
PII pre[N][N];//路径的前驱
//由于最短路性质,可以直接将当前节点前的一个结点作为前驱
int n,m;

void bfs()
{
    memset(d,-1,sizeof d);//用于判断是否是第一次访问到
    //一个点可以有多个路径到达,但是第一个到达的一定是最短路
    d[0][0]=0;
    int hh=0,tt=0;
    q[0]={0,0};
    int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
    while(hh<=tt)//只要非空
    {
       auto t=q[hh++];
       for(int i=0;i<4;i++)
       {
           int x=t.first+dx[i],y=t.second+dy[i];
           if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1)
           {
               d[x][y]=d[t.first][t.second]+1;
               q[++tt]={x,y};
               pre[x][y]=t;
           }
       }
    }
    int x=n-1,y=m-1;
    while(x||y)
    {
        cout<<x<<" "<<y<<endl;
        x=pre[x][y].first;
        y=pre[x][y].second;
    }
}

int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cin>>g[i][j];
    bfs();
    cout<<d[n-1][m-1];
    return 0;
}

三、邻接表邻接矩阵存图

1、邻接表的存法

2、使用h数组作为槽,利用e和ne数组和idx构造单链表存槽中相应结点有边相连的节点、

根据题意利用从1深搜,每一层用res存最大的子图的点数,每次计算出一个子连通图添加到sum中。

#include<bits/stdc++.h>
//846 树重心
using namespace std;
const int N=1e5+10,M=N*2;
typedef pair<int,int>PII;
int h[N],e[M],ne[M],idx;
bool st[N];
//h保存n个头结点
//在用数组模拟链表时,e保存链表结点值,ne保存边
//idx让这一切有序
int ans=N,n;//存结果
int dfs(int u)//u是结点的名字不是idx性质的
{
    st[u]=true;//标记这个结点已经被搜索过了
    //在遍历当前节点的所有子树之前
    int sum=1;//存所有子树的节点个数
    int res=0;//记录各个连通子图的节点个数
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j =e[i];
        if(st[j]==false)//只要这个结点的子树还没计算
        {
            int t=dfs(j);
            res=max(res,t);//存最大连通子图
            sum+=t;//所有子树
        }
    }
    res=max(res,n-sum);
    ans=min(ans,res);//保存最小的最大连通子图

    return sum;

}

void add(int a,int b)//头插法
{
  e[idx]=b;//每个idx都代表一个链表上的节点
  ne[idx]=h[a];
  h[a]=idx++;
}

int main()
{
    memset(h,-1,sizeof h);
    //memset(st,false,sizeof st);
    //所有结点的单链表指向的位置都为空
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    dfs(1);
    cout<<ans<<endl;

}

3、邻接表利用bfs计算最短路

#include<bits/stdc++.h>
//847图中点的层次
using namespace std;
const int N=1e5+10,M=2*N;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs()
{
    int hh=0,tt=0;
    memset(d,-1,sizeof d);
    q[0]=1;//1是结点的名字,入队
    d[1]=0;//到第一个结点的距离为0
    //数组模拟队列的时候hh永远指向队列的第一个元素,tt永远指向队尾,所以判断队列不为空的判断条件是hh<=tt。

    while(hh<=tt)
    {
      int t=q[hh++];//拿出队头元素
      for(int i=h[t];i!=-1;i=ne[i])//遍历与其相连的所有边
      {
          int j=e[i];//
          if(d[j]==-1)
          {
             d[j]=d[t]+1;
             q[++tt]=j;
          }

      }
    }
    return d[n];
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    cout<<bfs()<<endl;
    return 0;
}

4、有向无环图一定有拓扑序列,拓扑排序的实现

#include<bits/stdc++.h>
//848拓扑排序
using namespace std;
const int N=1e5+10,M=2*N;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];

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

bool topsort()
{
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++)
    {
        if(!d[i])q[++tt]=i;
    }
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i])
        {
           int j=e[i];
           d[j]--;
           if(!d[j])q[++tt]=j;

        }
    }
    return tt==n-1;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        d[b]++;
    }
    if(!topsort())puts("-1");
    else
    {
        for(int i=0;i<n;i++)cout<<q[i]<<" ";
        puts("");

    }
}

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

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

相关文章

flutter使用qr_code_scanner扫描二维码

qr_code_scanner仓库地址&#xff1a;qr_code_scanner | Flutter Package 需要添加android和ios的相机权限和本地相册权限&#xff1a; android中添加权限: 在android\app\build.gradle中修改&#xff1a;minSdkVersion 20 并且在android/app/src/main/AndroidManifest.xml中…

Kafka系列(一)【消息队列、Kafka的基本概念、Kafka的工作机制、Kafka可满足的需求、Kafka的特性、Kafka的应用场景】

kafka系列 一 一、消息队列1. 消息队列的来源2. 什么是消息队列3. 消息队列主要有哪些作用 二、Kafka的基本概念代理、生产者、消费者、消费者组主题、分区、副本、记录 三、了解 Kafka的工作机制-生产消息/消费消息四、Kafka可满足的需求五、Kafka的特性六、Kafka的场景 转自《…

漏洞挖掘 | 任意密码重置 + 存储型XSS

本文由掌控安全学院 - 老板来一份烧鹅饭 投稿 还是老样子&#xff0c;打开谷歌镜像&#xff0c;搜索site:edu.cn指定域名&#xff0c;搭配关键字登陆&#xff0c;注册&#xff0c;忘记密码&#xff0c;等等&#xff0c;或者xxx系统比较容易挖出通杀。 逻辑漏洞挖掘思路 1.登陆…

大带宽服务器托管的特点和考虑因素

很多公司和企业对于使用大带宽服务器的需求和存储不一样&#xff0c;为了满足不同的用户需求&#xff0c;大带宽服务器托管是个不错的选择&#xff0c;小编为您整理发布大带宽服务器托管的特点和要考虑的因素。 大带宽服务器托管是一种服务器托管服务&#xff0c;其主要特点是…

【数据分享】1929-2023年全球站点的逐年平均降水量(Shp\Excel\免费获取)

气象数据是在各项研究中都经常使用的数据&#xff0c;气象指标包括气温、风速、降水、湿度等指标&#xff0c;说到常用的降水数据&#xff0c;最详细的降水数据是具体到气象监测站点的降水数据&#xff01; 有关气象指标的监测站点数据&#xff0c;之前我们分享过1929-2023年全…

【图形学】投影和消隐简介

投影 正交投影 对于物体上任意一点的三维坐标P(x,y,z),投影后的三维坐标为 P ′ ( x ′ , y ′ , z ′ ) P^\prime(x^\prime,y^\prime,z^\prime) P′(x′,y′,z′),那么正交投影的方程为 { x ′ x y ′ y z ′ 0 \begin{cases} x^\primex\\y^\primey\\z^\prime0 \end{case…

2 月 7 日算法练习- 数据结构-并查集

并查集 并查集是一种图形数据结构&#xff0c;用于存储图中结点的连通关系。 每个结点有一个父亲&#xff0c;可以理解为“一只伸出去的手”&#xff0c;会指向另外一个点&#xff0c;初始时指向自己。 一个点的根节点是该点的父亲的父亲的的父亲&#xff0c;直到某个点的父亲…

【buuctf--来首歌吧】

用 Audacity 打开&#xff0c;左声道部分可以放大&#xff0c;可以按照长短转换成摩斯密码&#xff0c;放大后&#xff1a; ..... -... -.-. ----. ..--- ..... -.... ....- ----. -.-. -... ----- .---- ---.. ---.. ..-. ..... ..--- . -.... .---- --... -.. --... ----- -…

2024 年改变行业的人工智能主要趋势

1、导读 当我们迈入 2024 年时&#xff0c;了解人工智能趋势至关重要。它们不仅仅涉及技术进步&#xff1b;还涉及技术进步。它们意味着我们解决问题、做出决策和展望未来的方式发生了转变。本文旨在探索这些变革趋势&#xff0c;并强调人工智能如何不断突破可能性的界限&…

C++进阶(十二)lambda可变参数包装器

&#x1f4d8;北尘_&#xff1a;个人主页 &#x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上&#xff0c;不忘来时的初心 文章目录 一、新的类功能1、默认成员函数2、类成员变量初始化3、 强制生成默认函数的关键字default:4、…

【软件设计师笔记】深入探究操作系统

【软件设计师笔记】计算机系统基础知识考点(传送门) &#x1f496; 【软件设计师笔记】程序语言设计考点(传送门) &#x1f496; &#x1f413; 操作系统的作用 1.通过资源管理提高计算机系统的效率 2.改善人机界面向用户提供友好的工作环境 &#x1f413; 操作系统的特征 …

leetcode(滑动窗口)483.找到字符中所有字母异位词(C++详细解释)DAY4

文章目录 1.题目示例提示 2.解答思路3.实现代码结果 4.总结 1.题目 给定两个字符串 s 和 p&#xff0c;找到 s 中所有 p 的 异位词 的子串&#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串&#xff08;包括相同的字符串&a…

03-抓包_封包_协议_APP_小程序_PC应用_WEB应用

抓包_封包_协议_APP_小程序_PC应用_WEB应用 一、参考工具二、演示案例&#xff1a;2.1、WEB应用站点操作数据抓包-浏览器审查查看元素网络监听2.2、APP&小程序&PC抓包HTTP/S数据-Charles&Fiddler&Burpsuite2.3、程序进程&网络接口&其他协议抓包-WireSh…

three.js 向量方向(归一化.normalize)

效果&#xff1a; <template><div><el-container><el-main><div class"box-card-left"><div id"threejs" style"border: 1px solid red"></div><div><p><el-button type"primary…

c#: 表达式树的简化

环境&#xff1a; .net 6 一、问题&#xff1f; 有下面的表达式&#xff1a; var nums new List<int> { 1, 2, 3 }; Expression<Func<int, bool>> exp i > i > nums.Max();我们知道&#xff0c;它其实就是&#xff1a;exp i > i > 3; 那么…

史上最全嵌入式(学习路线、应用开发、驱动开发、推荐书籍、软硬件基础)

废话不多说直接上思维导图&#xff01; 如果有觉得图片看不清楚的&#xff0c;有疑问的&#xff0c;可在评论区进行留言&#xff01; 群号&#xff1a; 228447240 嵌入式总括 嵌入式书籍推荐 嵌入式软件知识 嵌入式硬件知识 嵌入式应用开发 嵌入式驱动开发 嵌入式视频推荐: 韦…

5秒搭建PalWorld幻兽帕鲁游戏服务器,你信吗?

5秒搭建PalWorld幻兽帕鲁游戏服务器&#xff0c;你信吗&#xff1f;腾讯云推出幻兽帕鲁专属镜像系统&#xff0c;直接选择镜像&#xff0c;5秒搞定&#xff0c;全自动化部署。 幻兽帕鲁太火了&#xff0c;官方palworld服务器不稳定&#xff1f;不如自建服务器&#xff0c;基于…

双归同一运营商的 BGP 部署

一、拓朴如下&#xff1a; 要求&#xff1a; 1、AS100 只接收 AS200 和 300 的路由&#xff0c;不接收其它 AS 的明细路由&#xff1b; 2、对于 AS100 的业务流量出方向&#xff0c;所有到 AS200 和 300 的流量&#xff0c;优先选择 Line-1&#xff0c;而到 AS400 的流…

SpringBoot Security安全认证框架初始化流程认证流程之源码分析

SpringBoot Security安全认证框架初始化流程&认证流程之源码分析 以RuoYi-Vue前后端分离版本为例分析SpringBoot Security安全认证框架初始化流程&认证流程的源码分析 目录 SpringBoot Security安全认证框架初始化流程&认证流程之源码分析一、SpringBoot Security安…

5.electron之主进程起一个本地服务

如果可以实现记得点赞分享&#xff0c;谢谢老铁&#xff5e; Electron是一个使用 JavaScript、HTML 和 CSS 构建桌面应用程序的框架。 Electron 将 Chromium 和 Node.js 嵌入到了一个二进制文件中&#xff0c;因此它允许你仅需一个代码仓库&#xff0c;就可以撰写支持 Windows、…