2023-8-28 图中点的层次(树与图的广度优先遍历)

这篇具有很好参考价值的文章主要介绍了2023-8-28 图中点的层次(树与图的广度优先遍历)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目链接:图中点的层次
2023-8-28 图中点的层次(树与图的广度优先遍历),宽度优先,算法文章来源地址https://www.toymoban.com/news/detail-678649.html

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int h[N], e[N], ne[N], idx;
int n, m;
int q[N], d[N];

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

int bfs()
{
    int hh = 0, tt = 0;
    q[0] = 1;
    memset(d, -1,sizeof d);
    d[1] = 0;
    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);
    
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    
    cout << bfs() <<endl;
    return 0; 
}

到了这里,关于2023-8-28 图中点的层次(树与图的广度优先遍历)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 学习高级数据结构:探索平衡树与图的高级算法

    🎉欢迎来到数据结构学习专栏~学习高级数据结构:探索平衡树与图的高级算法 ☆* o(≧▽≦)o *☆嗨~我是IT·陈寒🍹 ✨博客主页:IT·陈寒的博客 🎈该系列文章专栏:数据结构学习 📜其他专栏:Java学习路线 Java面试技巧 Java实战项目 AIGC人工智能 数据结构学习 🍹文章作者技

    2024年02月09日
    浏览(46)
  • 第五课 树与图

    题目描述 给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。 示例 1: 示例 2: 示例 3: 提示: 树中节点数目在范围 [0, 100] 内 -100 = Node.val = 100 代码展示 题目描述 给定一个 N 叉树,返回其节点值的 层序遍历 。(即从左到右,逐层遍历)。 树的序列化输入是用层序遍历

    2024年02月07日
    浏览(43)
  • 树与图c++

    前言 本文主要介绍的数据结构之树型结构的相关知识,树型数据结构是面试官面试的时候非常喜欢考的一种数据结构,树形结构的遍历也是大厂笔试非常喜欢设置的考点,这些内容都会在本篇文章中进行详细的介绍,并且还会介绍一些常用的算法。 一、树的基本概念 层次结

    2024年02月10日
    浏览(25)
  • 二叉树与图(C++刷题笔记)

    力扣 从根节点深度遍历二叉树,先序遍历时,将节点存储至path栈中,使用path_val累加节点值 当遍历到叶子节点,检查path_val是否为sum,若是,则将pathpush进入res的结果中去 在后续变量,将该节点从path栈中弹出,path_val减去节点值 题目代码 力扣 两个节点公共祖先一定从根节点

    2024年02月05日
    浏览(40)
  • 算法基础学习笔记——⑩DFS与BFS\树与图

    ✨博主:命运之光 ✨专栏:算法基础学习 目录 DFS与BFS树与图 ✨DFS ✨BFS 🍓宽搜流程图如下: 🍓宽搜流程: 🍓广搜模板 ✨树与图 🍓树是特殊的图(连通无环的图) 🍓树与图的存储: 🍓用宽搜框架来搜索图: 前言: 算法学习笔记记录日常分享,需要的看哈O(∩_∩)O,

    2024年02月09日
    浏览(34)
  • 第三章 搜索与图论(三)——最小生成树与二分图

    最小生成树针对无向图,有向图不会用到 Prim 求解稠密图的最小生成树 和Dijkstra的思想相似,两者都是基于贪心 区别在于Dijkstra求单源最短路,而Prim求最小生成树 最小生成树:用最少的边连通图中所有的点,使得这些边的权值和也最小 Prim中的 dis数组 含义:点到 集合 的最

    2024年02月13日
    浏览(52)
  • 【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数

    二分查找算法合集 动态规划汇总 视频算法专题 给你一个下标从 0 开始的 m x n 整数矩阵 grid 。你一开始的位置在 左上角 格子 (0, 0) 。 当你在格子 (i, j) 的时候,你可以移动到以下格子之一: 满足 j k = grid[i][j] + j 的格子 (i, k) (向右移动),或者 满足 i k = grid[i][j] + i 的格子

    2024年02月04日
    浏览(40)
  • 图的遍历——广度优先搜索

    广度优先搜索遍历类似于树的按层次遍历的过程。其过程为:假设从图中的某顶点v出发,在访问了v之后依次访问v的各个未曾被访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,

    2024年02月09日
    浏览(37)
  • 图的遍历 —— 广度优先遍历

    与树的遍历类似,图的遍历指从图的某一节点出发,按照某种搜索方式对图中的所有节点都仅访问一次。图的遍历可以解决很多搜索问题,实际应用非常广泛。图的遍历根据搜索方式的不同,分为广度优先遍历和深度优先遍历。 图的遍历 —— 广度优先遍历 广度优先搜索(

    2023年04月25日
    浏览(59)
  • 图的学习,深度和广度遍历

    表示“多对多”的关系 包括: 一组顶点:通常用V(Vertex)表示顶点集合 一组边:通常用E(Edge)表示边的集合 边是顶点对:(v, w)∈E,其中v,w∈V 有向边v, w表示从v指向w的边(单行线) 不考虑重边和自回路 类型名称:图(Graph) 数据对象集:G(V, E)由一个非空的有限顶点

    2024年02月09日
    浏览(36)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包