有向无权图最短路径问题——BFS求解

2024-02-02 01:48

文章标签 问题路径 bfs 求解无权

本文主要是介绍有向无权图最短路径问题——BFS求解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解释

有向无权图
图1

如图1所示，这是一个有向无权图，如果选中某个定点作为起始顶点s，我们要找出s到其他所有顶点的最短路径问题。由于是无权的，所以我们只关心最短路径所包含的边数。这就是一个有向无权图求最短路径的问题，用到BFS算法，广义优先搜索算法。

流程解析

设s为选中的v3。
找出所有从s出发路径长为1的顶点之后的图
从s出发路径长为1的顶点之后的图

此时可以看到从s出发到v3的最短路径长为0的路径，只有v3自己。把这个标记下来。然后寻找所有从s出发路径长为1的顶点，这些顶点可以通过考察s邻接的顶点找到。

找出所有从s出发路径长为1的顶点之后的图
现在寻找从s出发，最短路径为2 的顶点，找出所有邻接到v1和v6的顶点（距离为1处的顶点）。它们的最短路径还不知道，这次搜索告诉我们，到v2和v4的最短路径长为2。下图显示了到目前为止所做的工作。
这里写图片描述
找出所有从s出发路径长为2的顶点之后的图

最后通过考察那些邻接到刚被赋值的v2和v4的顶点可以发现，v5和v7各有一

这篇关于有向无权图最短路径问题——BFS求解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

http://www.chinasem.cn/article/669129。 23002807@qq.com

相关文章

hdu1254（嵌套bfs，两次bfs）

hdu1254（嵌套bfs，两次bfs）

/*第一次做这种题感觉很有压力，思路还是有点混乱，总是wa，改了好多次才ac的思路：把箱子的移动当做第一层bfs，队列节点要用到当前箱子坐标（x，y），走的次数step，当前人的weizhi（man_x，man_y），要判断人能否将箱子推到某点时要嵌套第二层bfs（人的移动）；代码如下：

阅读更多...

好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好）此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。按照除法的机制，用一个函数表示出来就可以了，代码如下

阅读更多...

hdu1043（八数码问题，广搜 + hash（实现状态压缩））

hdu1043（八数码问题，广搜 + hash（实现状态压缩））

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

阅读更多...

hdu2544（单源最短路径）

hdu2544（单源最短路径）

模板题： //题意：求1到n的最短路径，模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

阅读更多...

购买磨轮平衡机时应该注意什么问题和技巧

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时，您应该注意以下几个关键点：平衡精度平衡精度是衡量平衡机性能的核心指标，直接影响到不平衡量的检测与校准的准确性，从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声，提高磨削加工的精度。转速范围宽广的转速范围意味着平衡机能够处理更多种类的磨轮，适应不同的工作条件和规格要求。振动监测能力振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

阅读更多...

缓存雪崩问题

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库，瞬间耗尽数据库资源，导致数据库无法使用。解决方案： 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩缓存雪崩是指在短时间内，大量缓存数据同时失效，导致所有请求直接涌向数据库，瞬间增加数据库的负载压力，可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

阅读更多...

poj 1734 （floyd求最小环并打印路径）

poj 1734 （floyd求最小环并打印路径）

题意：求图中的一个最小环，并打印路径。解析： ans 保存最小环长度。一直wa，最后终于找到原因，inf开太大爆掉了。。。虽然0x3f3f3f3f用memset好用，但是还是有局限性。代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

阅读更多...

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题目录一.堆排序 1.1 思路 1.2 代码 1.3 简单测试二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）

阅读更多...

poj 2195 bfs+有流量限制的最小费用流

poj 2195 bfs+有流量限制的最小费用流

题意：给一张n * m（100 * 100）的图，图中” . " 代表空地， “ M ” 代表人， “ H ” 代表家。现在，要你安排每个人从他所在的地方移动到家里，每移动一格的消耗是1，求最小的消耗。人可以移动到家的那一格但是不进去。解析：先用bfs搞出每个M与每个H的距离。然后就是网络流的建图过程了，先抽象出源点s和汇点t。令源点与每个人相连，容量为1，费用为

阅读更多...

【VUE】跨域问题的概念，以及解决方法。

【VUE】跨域问题的概念，以及解决方法。

目录 1.跨域概念 2.解决方法 2.1 配置网络请求代理 2.2 使用@CrossOrigin 注解 2.3 通过配置文件实现跨域 2.4 添加 CorsWebFilter 来解决跨域问题 1.跨域概念跨域问题是由于浏览器实施了同源策略，该策略要求请求的域名、协议和端口必须与提供资源的服务相同。如果不相同，则需要服务器显式地允许这种跨域请求。一般在springbo

阅读更多...