搜索与图论(acwing算法基础)

这篇具有很好参考价值的文章主要介绍了搜索与图论(acwing算法基础)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

DFS

排列数字

#include<iostream>
using namespace std;
int n ;
int a[10];
bool s[10];
void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0 ; i <n ; i++) cout << a[i] << " " ;
        cout << endl ;
        return;
    }
    
    for(int i = 1; i <= n ; i++)
    {
        if(!s[i])
        {
            a[u] = i;
            s[i] = true ;
            dfs(u+1);
            a[u] = 0 ;
            s[i] = false;
        }
    }
    
    
}
int main()
{
    cin >> n ;
    dfs(0);
    return 0;
}

n皇后

#include<iostream>
using namespace std;
const int N = 20 ;
char g[N][N] ;
bool c[N], x[N] , y[N];
int n , m ;
void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0 ; i < n; i++) cout << g[i] << endl;
        cout << endl;
        return ;
    }
    for(int i = 0 ; i < n ; i++)
    {
        if(!c[i] && !x[u+i] && !y[u-i+n])
        {
            c[i] = x[u+i] = y[u-i+n] = true ;
            g[u][i] = 'Q';
            dfs(u+1);
            g[u][i] = '.';
            c[i] = x[u+i] = y[u-i+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);        
    return 0 ;
}

BFS

走迷宫

#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int,int> PII ;
const int N = 110 ;
PII q[N * N];
int f[N][N] , d[N][N];
int n , m ;
int dx[] = {0,1,0,-1} , dy[] = {1,0,-1,0} ;
int bfs()
{
    memset(d , -1 , sizeof d);
    d[1][1] = 0 ;
    q[0] = {1,1};
    int hh = 0 , tt = 0 ;
    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<=n &&x>0 && y<=m && y>0 && d[x][y] == -1 && f[x][y] == 0)
            {
               q[++tt] = {x,y};
               d[x][y] = d[t.first][t.second] + 1 ;
            }
        }
    }
    return d[n][m];
}
int main()
{
    cin >> n >> m ;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            cin >> f[i][j];
    
    cout << bfs();
    return 0;
}

拓扑序列

单链表

点击跳转至例题
搜索与图论(acwing算法基础)
搜索与图论(acwing算法基础)
idx存的是指针

树与图的深度优先搜索

树的重心
搜索与图论(acwing算法基础)

每个节点都是一个单链表

模拟队列

hh = 0 , tt = -1

有向图的拓扑序列

搜索与图论(acwing算法基础)
都是从前指向后,即有向无环图(不能有环)
所有入度为0的点,都能排在前面的位置

搜索与图论(acwing算法基础)
删掉t->j的边,仅仅是j的入度减一,当j的入度为0的时候,放入队列文章来源地址https://www.toymoban.com/news/detail-478062.html

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int n , m ;
int e[N] , h[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 topool()
{
    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] == 0) 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 x,y;
        cin >> x >> y;
        add(x,y);
        d[y]++;
    }
    if(topool())
    {
        for(int i = 0 ; i < n ; i++) cout << q[i] << " " ;
    }
    else cout << -1 ;
    return 0;
}

bellman-ford

有边数限制的最短路

spfa

spfa求最短路

spfa判断负环

Floyd

Floyd求最短路

Prim

Prim算法求最小生成树

Kruskal

Kruskal算法求最小生成树

染色法判定二分图

染色法判定二分图

到了这里,关于搜索与图论(acwing算法基础)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • ✔ ★ 算法基础笔记(Acwing)(三)—— 搜索与图论(17道题)【java版本】

    1. 排列数字(3分钟) 每次遍历dfs参数是 遍历的坑位 原题链接 2. n-皇后问题 原题链接 方法 1. 按行遍历(过程中有回溯、剪枝) 思想: 每次递归中,遍历一行的元素,如果可以放皇后,就递归到下一行,下一行中不行了,就返回来,回溯, 方法2. 按每个元素遍历(没有减枝)

    2024年02月05日
    浏览(48)
  • 第3章:搜索与图论【AcWing】

    阅读前导 本文默认读者有数据结构和图论基础,本文是对图论的几个代表性算法的入门,虽然题目的解法比较朴素,但是比较好理解。 首先简单复习一下离散数学中图论的相关概念。 图是由顶点和边组成,顶点一般表示对象,边一般表示对象之间的关系。 在图论中,多个顶

    2024年02月03日
    浏览(51)
  • 算法基础课-搜索与图论

    题目链接:842. 排列数字 - AcWing题库 思路:写的很好的题解AcWing 842. 排列数字--深度优先遍历代码+注释 - AcWing 也可以考虑使用c++自带的next_permutation函数直接秒了: 题目链接:844. 走迷宫 - AcWing题库 思路:由于bfs是一层一层扩展,所以能保证走到终点时,走过的距离最短,所

    2024年04月15日
    浏览(53)
  • 【算法基础:搜索与图论】3.3 拓扑排序

    https://oi-wiki.org/graph/topo/ 本文主要学习拓扑排序相关知识。 拓扑排序的英文名是 Topological sorting。 拓扑排序要解决的问题是给一个 有向无环图 的 所有节点排序 。 我们可以拿大学每学期排课的例子来描述这个过程,比如学习大学课程中有:程序设计,算法语言,高等数学,

    2024年02月16日
    浏览(50)
  • 【算法基础:搜索与图论】3.2 树与图的dfs和bfs

    要学会建树、建图的通用方法。 dfs 和 bfs 的代码框架。 https://www.acwing.com/problem/content/848/ 在 dfs 的过程中,统计各个节点作为断点时的连通块最大值。 https://www.acwing.com/problem/content/849/ 看到最短距离就可以想到使用宽搜。 注意! :题目中说明了 a 和 b 表示存在一条从 a 走到

    2024年02月16日
    浏览(39)
  • 【算法基础:搜索与图论】3.5 求最小生成树算法(Prim&Kruskal)

    最小生成树 有关树的定义 生成子图 :生成子图是从原图中选取部分节点以及这些节点之间的边所组成的图。生成子图中的所有节点和边都必须在原图中存在。 生成树 :一个连通 无向图 的 生成子图 ,同时要求是树。也即在图的边集中选择 n - 1 条,将所有顶点连通。 我们

    2024年02月16日
    浏览(40)
  • 【算法基础:搜索与图论】3.6 二分图(染色法判定二分图&匈牙利算法)

    https://oi-wiki.org/graph/bi-graph/ 二分图是图论中的一个概念, 它的所有节点可以被分为两个独立的集合,每个边的两个端点分别来自这两个不同的集合 。 换句话说, 二分图中不存在连接同一集合内两个节点的边 。 如何判断一个图是二分图? 当且仅当图中不含奇数环 。(奇数

    2024年02月16日
    浏览(43)
  • 【算法基础:搜索与图论】3.4 求最短路算法(Dijkstra&bellman-ford&spfa&Floyd)

    关于最短路可见:https://oi-wiki.org/graph/shortest-path/ 无向图 是一种 特殊的 有向图。(所以上面的知识地图上没有区分边有向还是无向) 关于存储:稠密图用邻接矩阵,稀疏图用邻接表。 朴素Dijkstra 和 堆优化Dijkstra算法的 选择就在于图 是 稠密的还是稀疏的。 算法步骤: 有一

    2024年02月16日
    浏览(45)
  • 算法基础复盘笔记Day07【搜索与图论】—— Prim、Kruskal、染色体判定二分图、匈牙利算法

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2024年02月02日
    浏览(50)
  • 算法基础复盘笔记Day06【搜索与图论】—— Dijkstra、bellman-ford、spfa、Floyd

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2023年04月22日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包