C++图的遍历实例分析

这篇文章主要介绍了C++图的遍历实例分析的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇C++图的遍历实例分析文章都会有所收获，下面我们一起来看看吧。要想遍历图，肯定要先储存图啊。下面我们采用邻接表来存图也可以看： 点这里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 ++ 。模板如下：方法：深度优先搜索的遍历顺序为一条路径走到底然后回溯再走下一条路径这种遍历方法很省内存但是不能一次性给出最短路径或者最优解。深度优先遍历的步骤访问顶点V依次从顶点V的未被访问的邻节点出发，进行深度优先搜索，直至和V有路径相通的顶点都被访问到。对于连通图进行遍历时，从一个顶点出发即可访问图中所有的顶点。对于非连通图进行遍历时，若图中尚有顶点未被访问，则另选一未曾访问的顶点作为起始点，进行深度优先搜索，直至所有顶点都被访问方法：从图的某一结点出发，首先依次访问该结点的所有邻接顶点（再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点，重复此过程，直至所有顶点均被访问为止。从顶点V出发广度优先搜索的步骤访问顶点V依次访问顶点V的各个未被访问的临接点（横向访问）从V的这些邻接点出发依次访问他们的邻接点，致使“先被访问的顶点的邻接点先于”后访问的顶点的邻接点”被访问(一般可以借助队列实现），直至图中所有已被访问的顶点的邻接点均被访问。对于非连通图进行遍历时，若图中尚有顶点未被访问，则另选一未曾访问的顶点作为起始点，进行广度优先搜索，直至所有顶点都被访问模板及注释图论算法中大量使用了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和BFS是图论算法的主要算法，其应用非常多，下面是一些常见例免费云主机域名子：1.无权图中求最短路径和最小生成树。2.检测环或圈。3.路径查找，使用DFS查找u到v的一条路径，使用栈stack作为辅助，使用递归算法遇到目标顶点v则入栈，后面陆续入栈，打印内容即为所求路径。4.拓扑排序：计算机中根据作业之间的关系来调度作业（或根据一定先后顺序优先级等）；计算机中的指令调度（先后顺序）；重新计算公式值公式单元的计算顺序；逻辑合成；makefile编译任务的执行顺序；数据序列化；编译器中的链接器中解决符号依赖关系。5.检测一个图是否是二分图。6.查找有向图的强连通分量，后面会详细讨论其实现算法。7.解决难题，如迷宫问题。关于“C++图的遍历实例分析”这篇文章的内容就介绍到这里，感谢各位的阅读！相信大家对“C++图的遍历实例分析”知识都有一定的了解，大家如果还想学习更多知识，欢迎关注百云主机行业资讯频道。

相关推荐: 向Spring IOC容器动态注册bean实现方式是什么

本篇内容主要讲解“向SpringIOC容器动态注册bean实现方式是什么”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“向SpringIOC容器动态注册bean实现方式是什么”吧!这周遇到了这样一个需求，从第三方的数…