算法起步之广度优先搜索

原文:算法起步之广度优先搜索

          广度优先搜索算法是图的基本算法之一，图是用来保存过对多的关系的数据结构，相对于树一对多的关系更为复杂，所以难度也会比树结构难一点，图的存储一般有连接表表示跟链接矩阵表示，相比来说链接矩阵的方式更为常用，也就是用数组来存储。而广度优先搜索算法其实就是图的遍历过程，数组的遍历大家都会，数组的遍历我们是按照下标的顺序来遍历的，而图的遍历也有自己的方式，图是多对多的关系，我们可以按照各个节点直接的关联关系来遍历他们，这样便衍生出来深度优先跟广度优先，广度优先是先访问与跟当前节点相关联的所有节点，而深度优先则是按照关联关系一层层的遍历。如下图：

          广度优先搜索我们需要借助一个队列，我们可以自己写一个队列，也可以借助linkedlist。

public class BFS {
	private LinkedList list=new LinkedList();

	public void BFS(int[][] map){
		 boolean[] visited=new boolean[map.length];
		 for (int i = 0; i < visited.length; i++) {
			if (!visited[i]) {
				list.addLast(i);
				while (!list.isEmpty()) {
					//访问队列里面的第一个节点
					int now=(Integer) list.removeFirst();
					visited[now]=true;
					// 将与该节点关联的且没有访问的节点加入到队列中。
					for (int j = 0; j < visited.length; j++) {
						if (map[now][j]==1&&!visited[j]) {
								list.addLast(j);
						}
					}
				}
			}
		}
	}
}

友情提示：转载请注明出处【作者：idlear  博客：http://blog.csdn.net/idlear】