当前位置：首页 > news >正文

算法-图-数据结构（邻接矩阵）-BFS广度优先遍历

news 2025/9/17 4:09:16

邻接矩阵广度优先遍历（BFS）是一种用于遍历或搜索图的算法，以下是具体介绍：

1. 基本概念
图是一种非线性的数据结构，由顶点和边组成，可分为无向图、有向图、加权图、无权图等。邻接矩阵是表示图的一种数据结构，是一个二维数组，其中行和列都对应图中的顶点。如果顶点i与顶点j之间存在一条边，则矩阵的第i行第j列的元素为1；否则为0[^4^]。
广度优先搜索是一种遍历或搜索图的算法，它按照从根节点到最远节点的层次顺序进行搜索。在邻接矩阵中，BFS可以使用队列实现。

2. 算法步骤
2.1 初始化队列，用于存储待访问的节点，并将起点加入队列。
2.1 标记已访问节点，通常使用一个数组来记录每个节点是否已被访问过，以避免重复访问。
2.3从队列中取出一个节点，检查该节点是否为目标节点。如果是，则搜索结束；如果不是，将其所有未访问的邻接节点加入队列，并标记为已访问。
重复步骤3，直到队列为空或找到目标节点

3.算法实现

图数据结构定义

package com.example.demo;
//邻接矩阵广度优先遍历
public class YuGraph {private String[] v;private int[][] vG;//默认空构造YuGraph(){}//初始赋值构造YuGraph(String[] v,int [][] vG ){this.v=v;this.vG=vG;}public String[] getV() {return v;}public void setV(String[] v) {this.v = v;}public int[][] getvG() {return vG;}public void setvG(int[][] vG) {this.vG = vG;}
}

BFS算法实现

package com.example.demo;import java.util.ArrayDeque;
import java.util.List;
import java.util.Queue;//广度优先遍历
public class YuTestBFS {//插入变的关系public static void insertBian(int [][] a, int i,int j){a[i][j]=1;}public static void bfsCreate(){//创建顶点String[] v=new String[]{"A","B","C","D","E"};//创建边int [][] vG=new int[v.length][v.length];//插入ab,bc,be,cdinsertBian(vG,0,1);//bcinsertBian(vG,1,2);//beinsertBian(vG,1,4);//cdinsertBian(vG,2,3);//创建邻接矩阵YuGraph graph=new  YuGraph(v,vG);//打印结果System.out.println("顶点");for(int i=0;i<graph.getV().length;i++){System.out.print(graph.getV()[i]);System.out.print(" ");}System.out.println();System.out.println("邻接矩阵");for(int i=0;i<graph.getvG().length;i++){for(int j=0;j<graph.getV().length;j++){System.out.print(graph.getvG()[i][j]);System.out.print(" ");}System.out.println();}//BFS访问实现//1.定义访问标记列表boolean [] flagArr=new boolean[v.length];for(int i=0;i<v.length;i++){flagArr[i]=false;}//2.定义辅助队列Queue<Integer> queue=new ArrayDeque<>();//A顶点入队queue.offer(0);flagArr[0]=true;System.out.print("BFS广度优先访问顶点:");System.out.print(v[0]);System.out.print(" ");//当队列不为空，逐层访问while (!queue.isEmpty()){//对头出队int vHead= queue.poll();//访问队头所在的邻接矩阵for(int i=0;i<v.length;i++){if(graph.getvG()[vHead][i]==1&&flagArr[i]==false){//访问System.out.print("访问 ");System.out.print(v[i]);System.out.print(" ");flagArr[i]=false;//被访问的点入队queue.offer(i);}}}}public static void main(String[] args) {bfsCreate();}
}

结果样例