无向图的BFS搜索

关于如何存储无向图的问题，想要详细了解的朋友可以阅读本人的另一篇博文存储无向图的邻接矩阵和邻接链表。

想更方便阅读代码的朋友可以点这里。

无向图的BFS遍历，其思想是，从某个点（该点可随机取得）一直把其邻接点走完，然后再将其邻接点的未被遍历的邻接点走完，如此反复直到走完所有结点。类似于树的层序遍历。所以我们需要一个visitd数组来表示当前点有没有被访问过。

算法流程：

1.访问指定起始点。

2.访问当前顶点的邻接顶点有未被访问的顶点，并将之放入队列中。

3.删除队列的队首节点。访问当前队列的队首，重复步骤2。直到队列为空。

4.若途中还有顶点未被访问，则再选一个点作为起始顶点。重复步骤2。（针对非连通图）。

程序代码如下：

package com.zengpeng.divide.classics.BFS;

/**

* 使用什么样的数据结构来存储无向图呢?

* 我们可以使用 图的临接矩阵 来表示

* @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;

}

//根据点Start判断与其相连的点 访问某点

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); //将第一个节点放入队列

while (!queue.isEmpty()) {

int current=queue.poll();

if(visited[current]==1) { //如果被访问过

continue;

}

ArrayList<Integer> points = visitPoint(current); //访问current点

for (Integer integer : points) {

if(visited[integer]==0) {  //未被访问过，添加到queue

System.out.println(nameArray[current]+"===>"+nameArray[integer]);

queue.add(integer);

}

}

visited[current]=1; //表示该点被访问过了

/**

* 该判断用于解决非连通图的遍历问题

*/

if(queue.isEmpty()&&checkVisited(visited)>=0) {

queue.add(checkVisited(visited));

}

}

}

//检查是否所有节点是否均被访问 若存在未访问的节点则返回未访问节点的index

public int checkVisited(int[] visited) {

for (int i=0;i<visited.length;i++) {

if(visited[i]==0) {

return i;

}

}

return -1;

}

}