關(guān)于如何存儲無向圖的問題，想要詳細(xì)了解的朋友可以閱讀本人的另一篇博文存儲無向圖的鄰接矩陣和鄰接鏈表。
想更方便閱讀代碼的朋友可以點(diǎn)這里。
無向圖的BFS遍歷，其思想是，從某個(gè)點(diǎn)（該點(diǎn)可隨機(jī)取得）一直把其鄰接點(diǎn)走完，然后再將其鄰接點(diǎn)的未被遍歷的鄰接點(diǎn)走完，如此反復(fù)直到走完所有結(jié)點(diǎn)。類似于樹的層序遍歷。所以我們需要一個(gè)visitd數(shù)組來表示當(dāng)前點(diǎn)有沒有被訪問過。
算法流程：
1.訪問指定起始點(diǎn)。
2.訪問當(dāng)前頂點(diǎn)的鄰接頂點(diǎn)有未被訪問的頂點(diǎn)，并將之放入隊(duì)列中。
3.刪除隊(duì)列的隊(duì)首節(jié)點(diǎn)。訪問當(dāng)前隊(duì)列的隊(duì)首，重復(fù)步驟2。直到隊(duì)列為空。
4.若途中還有頂點(diǎn)未被訪問，則再選一個(gè)點(diǎn)作為起始頂點(diǎn)。重復(fù)步驟2。（針對非連通圖）。
程序代碼如下：
package com.zengpeng.divide.classics.BFS;
/**
* 使用什么樣的數(shù)據(jù)結(jié)構(gòu)來存儲無向圖呢?
* 我們可以使用 圖的臨接矩陣 來表示
* @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) 訪問某點(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;
}
//通過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) { //如果被訪問過
continue;
}
ArrayList<Integer> points = visitPoint(current); //訪問current點(diǎn)
for (Integer integer : points) {
if(visited[integer]==0) {? //未被訪問過，添加到queue
System.out.println(nameArray[current]+"===>"+nameArray[integer]);
queue.add(integer);
}
}
visited[current]=1; //表示該點(diǎn)被訪問過了
/**
* 該判斷用于解決非連通圖的遍歷問題
*/
if(queue.isEmpty()&&checkVisited(visited)>=0) {
queue.add(checkVisited(visited));
}
}
}
//檢查是否所有節(jié)點(diǎn)是否均被訪問 若存在未訪問的節(jié)點(diǎ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;
}
}
