数据结构——广度优先搜索(BFS,Breadth First Search)

2023-10-28 10:59

本文主要是介绍数据结构——广度优先搜索(BFS,Breadth First Search),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一. 图遍历介绍

二. 广度优先遍历基本思想

三. 广度优先遍历算法步骤

四. 实例

五. 实现代码


一. 图遍历介绍

        所谓图的遍历,即是对结点的访问。一个图有那么多个结点,如何遍历这些结点,需要特定策略,一般有两种访问策略:

  • 深度优先遍历
  • 广度优先遍历

二. 广度优先遍历基本思想

图的广度优先搜索(Broad First Search) 。

类似于一个分层搜索的过程,广度优先遍历需要使用一个队列以保持访问过的结点的顺序,以便按这个顺序来访问这些结点的邻接结点


三. 广度优先遍历算法步骤

  1. 访问初始结点v并标记结点v为已访问。
  2. 结点v入队列
  3. 当队列非空时,继续执行,否则算法结束。
  4. 出队列,取得队头结点u。
  5. 查找结点u的第一个邻接结点w。
  6. 若结点u的邻接结点w不存在,则转到步骤3;否则循环执行以下三个步骤:
    1. 若结点w尚未被访问,则访问结点w并标记为已访问。
    2. 结点w入队列
    3. 查找结点u的继w邻接结点后的下一个邻接结点w,转到步骤6。

四. 实例

广度优先算法的遍历顺序为:1->2->3->4->5->6->7->8


五. 实现代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;public class Graph {private ArrayList<String> vertexList; //存储顶点集合private int[][] edges; //存储图对应的邻结矩阵private int numOfEdges; //表示边的数目//定义给数组boolean[], 记录某个结点是否被访问private boolean[] isVisited;public static void main(String[] args) {//测试一把图是否创建okint n = 8;  //结点的个数String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};//创建图对象Graph graph = new Graph(n);//循环的添加顶点for(String vertex: Vertexs) {graph.insertVertex(vertex);}//添加边graph.insertEdge(0, 1, 1);graph.insertEdge(0, 2, 1);graph.insertEdge(1, 3, 1);graph.insertEdge(1, 4, 1);graph.insertEdge(3, 7, 1);graph.insertEdge(4, 7, 1);graph.insertEdge(2, 5, 1);graph.insertEdge(2, 6, 1);graph.insertEdge(5, 6, 1);//显示邻结矩阵graph.showGraph();//测试,bfs遍历是否okSystem.out.println("广度优先!");graph.bfs(); // 1->2->3->4->5->6->7->8}//构造器public Graph(int n) {//初始化矩阵和vertexListedges = new int[n][n];vertexList = new ArrayList<String>(n);numOfEdges = 0;}//得到第一个邻接结点的下标 w /*** * @param index * @return 如果存在就返回对应的下标,否则返回-1*/public int getFirstNeighbor(int index) {for(int j = 0; j < vertexList.size(); j++) {if(edges[index][j] > 0) {return j;}}return -1;}//根据前一个邻接结点的下标来获取下一个邻接结点public int getNextNeighbor(int v1, int v2) {for(int j = v2 + 1; j < vertexList.size(); j++) {if(edges[v1][j] > 0) {return j;}}return -1;}//对一个结点进行广度优先遍历的方法private void bfs(boolean[] isVisited, int i) {int u ; // 表示队列的头结点对应下标int w ; // 邻接结点w//队列,记录结点访问的顺序LinkedList queue = new LinkedList();//访问结点,输出结点信息System.out.print(getValueByIndex(i) + "=>");//标记为已访问isVisited[i] = true;//将结点加入队列queue.addLast(i);while( !queue.isEmpty()) {//取出队列的头结点下标u = (Integer)queue.removeFirst();//得到第一个邻接结点的下标 w w = getFirstNeighbor(u);while(w != -1) {//找到//是否访问过if(!isVisited[w]) {System.out.print(getValueByIndex(w) + "=>");//标记已经访问isVisited[w] = true;//入队queue.addLast(w);}//以u为前驱点,找w后面的下一个邻结点w = getNextNeighbor(u, w); //体现出我们的广度优先}}} //遍历所有的结点,都进行广度优先搜索public void bfs() {isVisited = new boolean[vertexList.size()];for(int i = 0; i < getNumOfVertex(); i++) {if(!isVisited[i]) {bfs(isVisited, i);}}}//图中常用的方法//返回结点的个数public int getNumOfVertex() {return vertexList.size();}//显示图对应的矩阵public void showGraph() {for(int[] link : edges) {System.err.println(Arrays.toString(link));}}//得到边的数目public int getNumOfEdges() {return numOfEdges;}//返回结点i(下标)对应的数据 0->"A" 1->"B" 2->"C"public String getValueByIndex(int i) {return vertexList.get(i);}//返回v1和v2的权值public int getWeight(int v1, int v2) {return edges[v1][v2];}//插入结点public void insertVertex(String vertex) {vertexList.add(vertex);}//添加边/*** * @param v1 表示点的下标即使第几个顶点  "A"-"B" "A"->0 "B"->1* @param v2 第二个顶点对应的下标* @param weight 表示 */public void insertEdge(int v1, int v2, int weight) {edges[v1][v2] = weight;edges[v2][v1] = weight;numOfEdges++;}
}

这篇关于数据结构——广度优先搜索(BFS,Breadth First Search)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/292753

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

C# ComboBox下拉框实现搜索方式

《C#ComboBox下拉框实现搜索方式》文章介绍了如何在加载窗口时实现一个功能,并在ComboBox下拉框中添加键盘事件以实现搜索功能,由于数据不方便公开,作者表示理解并希望得到大家的指教... 目录C# ComboBox下拉框实现搜索步骤一步骤二步骤三总结C# ComboBox下拉框实现搜索步骤一这

hdu1254(嵌套bfs,两次bfs)

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

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

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)