算法：BFS 广度优先遍历

DFS与BFS  深度优先遍历与广度优先遍历的算法实现

 
             

 
 

BFS算法实现图的遍历

程序如下：

package algorithm;

import java.util.LinkedList;
import java.util.Queue;

public class Bfs {

	/**
	 * 好高深啊 广度优先遍历
	 */
	public static void main(String[] args) {

		// 以邻接矩阵表示树,设定初始值
		int[][] graph = new int[7][7];
		// 矩阵初始化，无向图，注意对角线的值全设为零，相对称的值设为相同
		// 最好先画图再设矩阵
		// 先全设为0表示无连接，再将有连接的地方改为1
		for (int i = 0; i < 6; i++) {
			for (int j = 0; j < 6; j++) {
				graph[i][j] = 0;
			}
		}
		
		graph[0][1] = 1;
		graph[1][0] = 1;
		graph[1][2] = 1;
		graph[2][1] = 1;
		graph[1][3] = 1;
		graph[3][1] = 1;
		graph[3][4] = 1;
		graph[4][3] = 1;
		graph[3][5] = 1;
		graph[5][3] = 1;
		graph[5][6] = 1;
		graph[6][5] = 1;
		// 设置标志数组，为0时表示当前节点没有访问过，为1时表示访问过了，初始化全部设0
		int[] mark = new int[graph.length];// graph.length返回的是第一维的维数，不是数组长度
		for (int k = 0; k < mark.length; k++) {
			mark[k] = 0;
		}
		// 设置队列，java里LinkedList实现了queue接口，所以用list就能表示队列
		Queue<Integer> queue = new LinkedList<Integer>();
		// 我们这里从0节点开始遍历
		if (mark[0] == 0)// mark[0]=0表示还没查看0节点，下面开始查看
		{
			mark[0] = 1;
			queue.add(0);
			while (!queue.isEmpty()) {
				// 取出队列值并输出
				int l = (Integer) queue.poll();
				// 最先放到队列里的值，注意队列的先进先出特性啊
				System.out.println("l=" + l);
				for (int n = 0; n < graph.length; n++) {
					// 如果为1，即表示有连接，且还未入队列，压入队列，设置当前值为-1，表示已经访问
					if (graph[l][n] == 1) {
						if (mark[n] != 1) {
							// 如果n节点没有访问过则入队列，否则不处理
							queue.add(n);
							mark[n] = 1;
						}
					}
				}
			}
		}
	}
}

 

队列queue变化：

 

 

BFS输出结果：

l=0
l=1
l=2
l=3
l=4
l=5
l=6