C++详细讲解图的遍历

目录
  • 图的遍历
    • 图的深度优先遍历(DFS, depth first search)
    • 图的宽度优先遍历(BFS, breadth first search)
    • 宽度优先搜索BFS的应用
    • 深度优先遍历DFS的应用

图的遍历

要想遍历图,肯定要先储存图啊。

下面我们采用邻接表来存图

也可以看: 点这里

1.用 h 数组保存各个节点能到的第一个节点的编号。开始时,h[i] 全部为 -1。

2.用 e 数组保存节点编号,ne 数组保存 e 数组对应位置的下一个节点所在的索引。

3.用 idx 保存下一个 e 数组中,可以放入节点位置的索引

4.插入边使用的头插法,例如插入:a->b。首先把b节点存入e数组,e[idx] = b。然后 b 节点的后继是h[a],ne[idx] = h[a]。最后,a 的后继更新为 b 节点的编号,h[a] = idx,索引指向下一个可以存储节点的位置,idx ++ 。

模板如下:

//邻接表
const int N = 100010, M = N * 2;
//无向图n条边时,最多2n个idx,因为每条边在邻接表中会出现两次
int h[N], e[M], ne[M], idx;
//n个链表头,e每一个结点的值,ne每一个结点的next指针
void add(int a, int b)//a->b
{//e记录当前点的值(地址->值),ne下一点的地址(地址->地址),h记录指向的第一个点的地址(值->地址)
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}//头插法
// 初始化
idx = 0;
memset(h, -1, sizeof h);

图的深度优先遍历(DFS, depth first search)

方法:深度优先搜索的遍历顺序为一条路径走到底然后回溯再走下一条路径这种遍历方法很省内存但是不能一次性给出最短路径或者最优解。

深度优先遍历的步骤

  1. 访问顶点V
  2. 依次从顶点V的未被访问的邻节点出发,进行深度优先搜索,直至和V有路径相通的顶点都被访问到。
  3. 对于连通图进行遍历时,从一个顶点出发即可访问图中所有的顶点。
  4. 对于非连通图进行遍历时,若图中尚有顶点未被访问,则另选一未曾访问的顶点作为起始点,进行深度优先搜索,直至所有顶点都被访问
// 需要标记数组st[N],  遍历节点的每个相邻的点
void dfs(int u) {
    st[u] = true; // 标记一下,记录为已经被搜索过了,下面进行搜索过程
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
//因为每个节点的编号都是不一样的,所以 用编号为下标 来标记是否被访问过
        if (!st[j]) {
            dfs(j);
        }
    }
}

图的宽度优先遍历(BFS, breadth first search)

方法:从图的某一结点出发,首先依次访问该结点的所有邻接顶点(再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点,重复此过程,直至所有顶点均被访问为止。

从顶点V出发广度优先搜索的步骤

  1. 访问顶点V
  2. 依次访问顶点V的各个未被访问的临接点(横向访问)
  3. 从V的这些邻接点出发依次访问他们的邻接点,致使“先被访问的顶点的邻接点先于"后访问的顶点的邻接点"被访问(一般可以借助队列实现),直至图中所有已被访问的顶点的邻接点均被访问。
  4. 对于非连通图进行遍历时,若图中尚有顶点未被访问,则另选一未曾访问的顶点作为起始点,进行广度优先搜索,直至所有顶点都被访问

模板及注释

queue<int> q;//借助队列实现
st[1] = true; // 表示1号点已经被遍历过
q.push(1);//1号节点入队列
while (q.size())//对列非空,就一直往后搜索
{
    int t = q.front();//队头出队,找该点能到的点
    q.pop();//遍历完就出队列
    for (int i = h[t]; i != -1; i = ne[i])//遍历所有t节点能到的点,i为节点索引
    {
        int j = e[i];//通过索引i得到t能到的节点编号
        if (!st[j])//如果没有遍历过
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);//节点入队
        }
    }
}

宽度优先搜索BFS的应用

图论算法中大量使用了BFS或类似的算法,其常见的应用如下:

1.求最短路径路径和最小生成树,两个顶点的最短路径是指两个顶点间含有最少顶点的路径,另外最小生成树也可以使用DFS。

2.P2P网络中查找临近的结点,应用场景如P2P文件下载,P2P语音视频通信。

3.搜索引擎的网络爬虫的主要算法之一,DFS也是。

4.社交网络网站,在社交网络中可以搜索k层级以内查找一个人。

5.GPS导航系统,使用BFS查找附近地点等。

6.网络广播,在网络中使用BFS将广播包发送给每个节点。 垃圾回收算法,例如Cheney算法。

7.无向图环或圈检测,BFS和DFS都可以检测无向图的环或圈,有向图环检测只能使用DFS。

8.查找最大流,如下面会谈到的Ford-Fulkerson算法。

9.检测一个图是否是一个二分图,DFS和BFS都可以。

10.路径查找,使用BFS和DFS检测两个顶点是否有一条路径,查找一个顶点到所有可达到的顶点等等。

深度优先遍历DFS的应用

DFS和BFS是图论算法的主要算法,其应用非常多,下面是一些常见例子:

1.无权图中求最短路径和最小生成树。

2.检测环或圈。

3.路径查找,使用DFS查找u到v的一条路径,使用栈stack作为辅助,使用递归算法遇到目标顶点v则入栈,后面陆续入栈,打印内容即为所求路径。

4.拓扑排序:计算机中根据作业之间的关系来调度作业(或根据一定先后顺序优先级等);计算机中的指令调度(先后顺序);重新计算公式值公式单元的计算顺序;逻辑合成;makefile编译任务的执行顺序;数据序列化;编译器中的链接器中解决符号依赖关系。

5.检测一个图是否是二分图。

6.查找有向图的强连通分量,后面会详细讨论其实现算法。

7.解决难题,如迷宫问题。

到此这篇关于C++详细讲解图的遍历的文章就介绍到这了,更多相关C++图的遍历内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++详细讲解图论的基础与图的储存

    目录 一.前言 二.图的定义 三.图的储存 1.邻接矩阵 2.邻接表 3.邻接矩阵与邻接表的优缺点对比 一.前言 在算法中一般都需要把问题抽象成图论问题然后用图论的算法解决问题. 图论涉及相当多的算法,包括图DFS和BFS.连通性.拓扑排序.最小生成树.最短路径.最大流网络.图的着色问题等等 图论算法在计算机科学中扮演着很重要的角色,它提供了对很多问题都有效的一种简单而系统的建模方式.很多问题都可以转化为图论问题,然后用图论的基本算法加以解决. 二.图的定义 图(graph) 如上图是一个图G,

  • C++实现拓扑排序(AOV网络)

    本文实例为大家分享了C++实现拓扑排序的具体代码,供大家参考,具体内容如下 一.思路 先扫描所有顶点,把入度为0的顶点(如C,E)进栈.然后,取栈顶元素,退栈,输出取得的栈顶元素v(即入度为0的顶点v).接着,把顶点v的邻接顶点w的入度减1,如果w的入度变为0,则进栈.接着,取顶点w的兄弟结点(即取顶点v的邻接顶点w的下一邻接顶点),做同样的操作.重复上面步骤,直到输出n个顶点. 如上图: (1)扫描所有顶点,把入度为0的顶点进栈:将顶点C,E进栈: (2)取栈顶元素,退栈,输出取得的栈顶元素E

  • C++详细讲解图的拓扑排序

    目录 一.前言 二.算法流程 三.有向图的拓扑排序 一.前言 且该序列必须满足下面两个条件: 每个顶点出现且只出现一次. 若存在一条从顶点 x到顶点 y的路径,那么在序列中顶点 x 出现在顶点 y的前面. 拓扑排序只适用于 AOV网 (有向无环图) 若图中有环,则一定不存在拓扑序. 可以证明,一个有向无环图,一定存在一个拓扑序列.有向无环图,又被称为拓扑图. 入度: 即有多少条边指向自己这个节点. 出度: 即有多少条边从自己这个节点指出去. 二.算法流程 算法流程: 用队列来执行 ,初始化所有入

  • 详解C++实现拓扑排序算法

    一.拓扑排序的介绍 拓扑排序对应施工的流程图具有特别重要的作用,它可以决定哪些子工程必须要先执行,哪些子工程要在某些工程执行后才可以执行.为了形象地反映出整个工程中各个子工程(活动)之间的先后关系,可用一个有向图来表示,图中的顶点代表活动(子工程),图中的有向边代表活动的先后关系,即有向边的起点的活动是终点活动的前序活动,只有当起点活动完成之后,其终点活动才能进行.通常,我们把这种顶点表示活动.边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network),简

  • C++详细讲解图的遍历

    目录 图的遍历 图的深度优先遍历(DFS, depth first search) 图的宽度优先遍历(BFS, breadth first search) 宽度优先搜索BFS的应用 深度优先遍历DFS的应用 图的遍历 要想遍历图,肯定要先储存图啊. 下面我们采用邻接表来存图 也可以看: 点这里 1.用 h 数组保存各个节点能到的第一个节点的编号.开始时,h[i] 全部为 -1. 2.用 e 数组保存节点编号,ne 数组保存 e 数组对应位置的下一个节点所在的索引. 3.用 idx 保存下一个 e

  • C语言详细讲解树状数组与线段树

    目录 树状数组 动态求连续区间和 数星星 线段树 动态求连续区间和 数列区间最大值 树状数组 动态求连续区间和 给定 n 个数组成的一个数列,规定有两种操作,一是修改某个元素,二是求子数列 [a,b] 的连续和. 输入格式第一行包含两个整数 n 和 m,分别表示数的个数和操作次数. 第二行包含 n 个整数,表示完整数列. 接下来 m 行,每行包含三个整数 k,a,b (k=0,表示求子数列[a,b]的和:k=1,表示第 a 个数加 b). 数列从 1 开始计数. 输出格式输出若干行数字,表示 k

  • C++超详细讲解树与二叉树

    目录 树 树的定义 树的名词解释 树的表示 树的存储结构 二叉树的概念及结构 二叉树的概念 二叉树的性质 二叉树的存储结构 顺序存储结构 链式存储结构 树 树的定义 Q:什么是树 A:树是一种 非线性 的数据结构,它是由 n ( n>=0 )个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的. Q:树有什么特点 有一个特殊的结点,称为根结点,根节点没有前驱结点. 除根节点外,其余结点被分成M(M>0)个互不相交的集合T1.T2.…….T

  • C++超详细实现二叉树的遍历

    目录 二叉树的遍历 前序遍历 中序遍历 后序遍历 层序遍历 二叉树的遍历 Q:什么是二叉树的遍历? A:二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次,且仅被访问一次. Q:二叉树有几种遍历方法? A:二叉树的遍历方法可以有很多种,如果限制了从左到右的习惯方式,那么主要分为以下四种:先序遍历,中序遍历,后序遍历,层序遍历. 前序遍历 Q:什么是先序遍历 A:先序遍历就是先访问树的根节点,再访问树的左子节点,再访问右子节点.可以想象为,从一棵二叉树根节点

  • 详解JS对象遍历的顺序问题

    可能有些同学听过在 JavaScript 中遍历对象顺序不固定的这一说法.事实上,这个说法不是特别准确. 对待遍历顺序,对象有一套自己既定的规则,在此规则下呢,对象的遍历顺序会受插入元素顺序的影响,但是不完全受插入元素先后顺序的影响.如果您有「必须按插入元素顺序遍历」的场景,可以考虑使用 Map. 遍历对象的方法有很多种,我们经常会使用的有 for...in ,除此之外,还有: Object.keys Object.entries Obejct.getOwnerProPertyNames Ref

  • 使用pyinstaller打包.exe文件的详细教程

    为什么要打包? 1:当你想把你做的python游戏或者是脚本等.py文件发给别人时,打包为.exe文件,即使对方没有安装python也能运行 2:单纯想秀一下hhh 安装pyinstaller 安装pyinstaller很简单,直接cmd使用pip命令即可 pip install pyinstaller pyinstaller打包单个.py文件步骤 使用之前做的时钟为例进行演示 1:单击以下区域输入cmd切换到目标文件目录 2:输入pyinstaller -F -w Analog_clock.p

  • C++超详细讲解构造函数

    目录 类的6个默认成员函数 构造函数 特性 编译器生成的默认构造函数 成员变量的命名风格 类的6个默认成员函数 如果我们写了一个类,这个类我们只写了成员变量没有定义成员函数,那么这个类中就没有函数了吗?并不是的,在我们定义类时即使我们没有写任何成员函数,编译器会自动生成下面6个默认成员函数. class S { public: int _a; }; 这里就来详细介绍一下构造函数. 构造函数 使用C语言,我们用结构体创建一个变量时,变量的内容都是随机值,要想要能正确的操作变量中存储的数据,我们还需

  • Python 内置logging 使用详细介绍

    目录 logging 的主要作用 logging 日志等级 logging 的基础函数 logging 的四大组件(类) logging 的配置 logging 和 print 的区别 主要参考资料 logging 的主要作用 提供日志记录的接口和众多处理模块,供用户存储各种格式的日志,帮助调试程序或者记录程序运行过程中的输出信息. logging 日志等级 logging 日志等级分为五个等级,优先级从高到低依次是 : **CRITICAL; ** 程序严重错误 **ERROR; **程序错误

  • Vue3组件库框架搭建example环境的详细教程

    目录 1 搭建 example 开发环境 1.1 创建 example 项目 1.2 修改 package.json 1.3 修改 vite 配置文件 1.4 多环境支持 1.5 测试启动服务 2 测试 foo 组件 2.1 安装依赖 2.2 引入组件库 2.3 使用组件 2.4 运行查看效果 3 example 打包构建 前面用了大量篇幅介绍组件库的开发环境搭建,包括:创建组件.创建组件库入口.组件库样式架构.组件库公共包,做了一大堆工作,还不能预览示例组件 foo,本文便搭建 example

随机推荐