深圳成品网站超市,企业网站运行通知,专业建站团队,天津网站制作网页邻接矩阵广度优先遍历#xff08;BFS#xff09;是一种用于遍历或搜索图的算法#xff0c;以下是具体介绍#xff1a;
1. 基本概念 图是一种非线性的数据结构#xff0c;由顶点和边组成#xff0c;可分为无向图、有向图、加权图、无权图等。邻接矩阵是表示图的一种数…邻接矩阵广度优先遍历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.vv;this.vGvG;}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[] vnew String[]{A,B,C,D,E};//创建边int [][] vGnew 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 graphnew YuGraph(v,vG);//打印结果System.out.println(顶点);for(int i0;igraph.getV().length;i){System.out.print(graph.getV()[i]);System.out.print( );}System.out.println();System.out.println(邻接矩阵);for(int i0;igraph.getvG().length;i){for(int j0;jgraph.getV().length;j){System.out.print(graph.getvG()[i][j]);System.out.print( );}System.out.println();}//BFS访问实现//1.定义访问标记列表boolean [] flagArrnew boolean[v.length];for(int i0;iv.length;i){flagArr[i]false;}//2.定义辅助队列QueueInteger queuenew 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 i0;iv.length;i){if(graph.getvG()[vHead][i]1flagArr[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();}
}结果样例
