鄰接矩陣廣度優先遍歷（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();}
}
結果樣例
)
)
)
