關(guān)于如何存儲(chǔ)無(wú)向圖的問(wèn)題锐墙，想要詳細(xì)了解的朋友可以閱讀本人的另一篇博文存儲(chǔ)無(wú)向圖的鄰接矩陣和鄰接鏈表酷鸦。
想更方便閱讀代碼的朋友可以點(diǎn)這里。
無(wú)向圖的BFS遍歷嬉橙，其思想是，從某個(gè)點(diǎn)（該點(diǎn)可隨機(jī)取得）一直把其鄰接點(diǎn)走完寥假，然后再將其鄰接點(diǎn)的未被遍歷的鄰接點(diǎn)走完市框，如此反復(fù)直到走完所有結(jié)點(diǎn)。類似于樹的層序遍歷糕韧。所以我們需要一個(gè)visitd數(shù)組來(lái)表示當(dāng)前點(diǎn)有沒(méi)有被訪問(wèn)過(guò)枫振。
算法流程：
1.訪問(wèn)指定起始點(diǎn)喻圃。
2.訪問(wèn)當(dāng)前頂點(diǎn)的鄰接頂點(diǎn)有未被訪問(wèn)的頂點(diǎn)，并將之放入隊(duì)列中粪滤。
3.刪除隊(duì)列的隊(duì)首節(jié)點(diǎn)斧拍。訪問(wèn)當(dāng)前隊(duì)列的隊(duì)首，重復(fù)步驟2杖小。直到隊(duì)列為空肆汹。
4.若途中還有頂點(diǎn)未被訪問(wèn)，則再選一個(gè)點(diǎn)作為起始頂點(diǎn)予权。重復(fù)步驟2昂勉。（針對(duì)非連通圖）。
程序代碼如下：
package com.zengpeng.divide.classics.BFS;
/**
* 使用什么樣的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)無(wú)向圖呢?
* 我們可以使用 圖的臨接矩陣 來(lái)表示
* @author?
*
*/
import java.util.ArrayList;
import java.util.LinkedList;
public class Graph {
public int[][] adjacencyMatrix;? //鄰接矩陣
public String[] nameArray;
public Graph(int[][] adjacencyMatrix,String[] nameArray) {
this.adjacencyMatrix=adjacencyMatrix;
this.nameArray=nameArray;
}
//根據(jù)點(diǎn)Start判斷與其相連的點(diǎn) 訪問(wèn)某點(diǎn)
public ArrayList<Integer> visitPoint(int start){
ArrayList<Integer> points=new ArrayList<Integer>(adjacencyMatrix.length);
for(int j=0;j<adjacencyMatrix[0].length;j++) {
if(adjacencyMatrix[start][j]>0) {
points.add(j);
}
}
return points;
}
//通過(guò)BFS遍歷圖(輸出線段)
public void grathBFS() {
int[] visited=new int[adjacencyMatrix.length];
LinkedList<Integer> queue=new LinkedList<Integer>();
int i=1;
queue.add(i); //將第一個(gè)節(jié)點(diǎn)放入隊(duì)列
while (!queue.isEmpty()) {
int current=queue.poll();
if(visited[current]==1) { //如果被訪問(wèn)過(guò)
continue;
}
ArrayList<Integer> points = visitPoint(current); //訪問(wèn)current點(diǎn)
for (Integer integer : points) {
if(visited[integer]==0) {? //未被訪問(wèn)過(guò)伟件，添加到queue
System.out.println(nameArray[current]+"===>"+nameArray[integer]);
queue.add(integer);
}
}
visited[current]=1; //表示該點(diǎn)被訪問(wèn)過(guò)了
/**
* 該判斷用于解決非連通圖的遍歷問(wèn)題
*/
if(queue.isEmpty()&&checkVisited(visited)>=0) {
queue.add(checkVisited(visited));
}
}
}
//檢查是否所有節(jié)點(diǎn)是否均被訪問(wèn) 若存在未訪問(wèn)的節(jié)點(diǎn)則返回未訪問(wèn)節(jié)點(diǎn)的index
public int checkVisited(int[] visited) {
for (int i=0;i<visited.length;i++) {
if(visited[i]==0) {
return i;
}
}
return -1;
}
}
