基础算法(三)——广度优先搜索

广度优先搜索(Breadth First Search),是很多重要的图的算法的原型。

重要的作用:遍历。对于图的遍历,一般有以下的基本思想:

①从图中某个顶点V0出发,并访问此顶点;

②从V0出发,访问V0的各个未曾访问的邻接点W1,W2,…,Wk;然后,依此从W1,W2,…,Wk

出发访问各自未被访问的邻接点。

③重复②,直到全部顶点都被访问为止。

【例】如图1-7,按照广度优先搜索的思想遍历这张图。

正确的方法应该是:

【例】编写“连连看”的简单程序

规则是:相连不超过两个弯的相同图形是可以消去的。

写这个程序的时候的基本步骤:

1. 判断是否能消去

2. 消去/不消去,提示信息

重点应用BFS的是在第一个步骤中:

①图形是否相等非常简单,只要判断该处元素的值即可;
②相连是否不超过两个弯,我们需要从中取一个结点为起始点,先拿到无须转弯就能到达的结点集合A,看目标结点是否在里面;如果不在,则需要对结点集合A中所有结点,拿到其无须转弯就能到达的结点(未在之前访问过),判断目标结点是否在内;如果不在,则继续扩展,这次如果再不在,说明两结点连接超过两个弯了,不满足。

【重点】广度优先的缺点是:有的时候耗时会很大,这时候可以使用哈希表进行优化。在此不会特别用到,故不再细述。广度优先搜索与深度有限搜索是两个相对的搜索方法。对于广度优先搜索,一般的最短路径会用到它。

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。注意该算法要求图中不存在负权边。

【例】在无向图 G=(V,E) 中,假设每条边 E[i] 的长度为 w[i],找到由顶点 V0 到其余各点的最短路径。(单源最短路径)例如图1-8所示:
第一步:先锁定一个点,这里我用A作为初始的;

第二步:先设A到所有的点的路径的长度为无穷大,然后按照图1-9的步骤一步一步做就可以得到答案。


回顾:这里面当选定一个点的时候,就对其可连接到的点进行BFS,所以当问题可以抽象成类似于这个样子就可以进行BFS进行查找答案(最短路径)。

这是我从博客园上找到的完整的解题思路供参考:

对于以下的无向图(图1-10)进行遍历

图1-10 无向图例题

解答过程见图1-11.


图1-11 图1-10的解答过程

下面是Floyd算法。

Floyd算法是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题,同时也被用于计算有向图的传递闭包。Floyd算法的时间复杂度为O(N?)(有点费时间),空间复杂度为O(N?)。

以下的例题和解题过程来自博客园:

基本解题思路:

a.从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。   

b.对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

对于这种题目,我们一般使用的是十字交叉法如图1-12:


图1-12 十字交叉法

时间: 08-11

基础算法(三)——广度优先搜索的相关文章

算法_图的深度优先搜索和广度优先搜索

一.图的基本数据结构 图是由一组顶点和一组能够将两个顶点相互连接的边所构成的,一般使用0~V-1这样的数字形式来表示一张含有V个顶点的图.用v-w来指代一张图的边,由于是无向图,因此v-w和w-v是同一种边的两种表示方法.无向图是指边没有方向的图结构在无向图中,边仅仅表示的是两个顶点之间的连接.图的数据结构的可视化如下图所示(其中边上的箭头没有任何意义): 当两个顶点通过一条边相互连接,则称这两个顶点是相邻的.某个顶点的度数即为依附它的边的总数.当两个顶点之间存在一条连接双方的路径的时候,称为这

Dijkstra算法(三)之 Java详解

前面分别通过C和C++实现了迪杰斯特拉算法,本文介绍迪杰斯特拉算法的Java实现. 目录 1. 迪杰斯特拉算法介绍 2. 迪杰斯特拉算法图解 3. 迪杰斯特拉算法的代码说明 4. 迪杰斯特拉算法的源码 转载请注明出处:http://www.cnblogs.com/skywang12345/ 更多内容:数据结构与算法系列 目录 迪杰斯特拉算法介绍 迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径. 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想

广度优先搜索总结

广度优先搜索是对无向图以逻辑上的树的形式从根节点开始进行的逐层遍历. 当题目所求为路径某属性最小的解时适用广度优先搜索,因为如果能使逻辑上的树的层数和所求的最小的属性严格一致,逐层遍历到终点时必然为其属性最小值. 算法实现:基于(优先)队列先进先出的特性,实现优先遍历上层节点,通过标记数组保证访问过的点不被多次访问. 将根节点入队,在while(!q.empty())循环中将队首取出,并建立其子节点信息,如果子节点是合法的就入队并标记,直到找到答案或队列为空表示未找到. 注意问题:1.初始化标记

若干经典基础算法题目练习

练习1,判断是否为素数: // ConsoleAppIsPrime1.cpp : 定义控制台应用程序的入口点. // /* *函数功能:判断一个输入的数是否为素数 *函数原形:bool Prime( int x ) *参数:int x:将要判断的数 *返回值:bool型变量,判断是否是素数 *备注:需要包含头文件<math.h> *日期:2014/11/25 *原创:否 *作者:EbowTang *Email:[email protected] */ #include "stdafx

20_Shell语言———VIM编辑器基础知识三之窗口属性定制、配置文件及查找替换功能

Vim编辑器可以让用户按照需求来定制一些使用属性. 一.窗口属性定义 1)显示行号 行号不是内容,只是用来帮助用户确认文本所在的行.在vim编辑器中,如果要显示行号,可以在末行模式下输入: set number 如果想关闭,则可以在功能名称前面加上no,即: set nonumber 命令可以被简写,如set number 可以简写为 set nu:set nonumber 可以简写为 set nonu. 注意,上述设定仅对当前vim的进程有效,一旦当前进程关闭,这些设定就会失效,如果要使设定永

九章算法 基础算法 强化算法 系统设计 大数据 安卓 leetcode 高清视频

leetcode 直播视频讲座录像 九章算法视频录像,PPT 算法班,算法强化班,Java入门与基础算法班,big data项目实战班,Andriod项目实战班 九章算法下载 九章算法面试 九章算法leetcode 九章算法答案 九章算法mitbbs 九章算法班 九章算法ppt 九章算法录像 九章算法培训 九章算法微博 leetcode 视频 九章算法偷录 算法培训 算法班课程大纲: 1 从strStr谈面试技巧与Coding Style(免费试听) 2 二分搜索与旋转排序数组 Binary S

SDUT 2141 【TEST】数据结构实验图论一:基于邻接矩阵的广度优先搜索遍历

数据结构实验图论一:基于邻接矩阵的广度优先搜索遍历 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Discuss Problem Description 给定一个无向连通图,顶点编号从0到n-1,用广度优先搜索(BFS)遍历,输出从某个顶点出发的遍历序列.(同一个结点的同层邻接点,节点编号小的优先遍历) Input 输入第一行为整数n(0< n <100),表示数据的组数.对于每组数据,第一行是三个整数k,m,t(0<

算法录 之 基础算法

这一篇文章主要说说一些基础算法,这些算是很多其他算法的基石. 主要包括  模拟,暴力,枚举,递归,贪心,分治. 1,模拟: 顾名思义,模拟就是...饿,模拟,有一些题目就是给你一些步骤,然后你写代码一步步去模拟那些步骤就行.这类题目主要属于基础题,但是当然如果需要模拟的步骤足够恶心的话,还是比较麻烦的... 具体模拟的例子在之后的练习中会遇到的,按照题目要求一步步做就行,一般算法难度比较小. 2,暴力: 顾名思义,暴力就是...饿,暴力.比如说题目让从平面上的10个点中取三个点,让他们形成的三角

数据结构实验之图论二:基于邻接表的广度优先搜索遍历

数据结构实验之图论二:基于邻接表的广度优先搜索遍历 Time Limit: 1000ms   Memory limit: 65536K  有疑问?点这里^_^ 题目描述 给定一个无向连通图,顶点编号从0到n-1,用广度优先搜索(BFS)遍历,输出从某个顶点出发的遍历序列.(同一个结点的同层邻接点,节点编号小的优先遍历) 输入 输入第一行为整数n(0< n <100),表示数据的组数. 对于每组数据,第一行是三个整数k,m,t(0<k<100,0<m<(k-1)*k/2,