广度优先搜索算法案例及java代码实现

广度优先搜索算法（Breadth First Search），又称“广度优先搜索”或“水平优先搜索”，简称BFS； BFS 用于图搜索算法（要求能够使用图来表示问题之间的关系）。

BFS 可以用来解决两类问题：

• 是否有从 A 到 B 的路径？
• 从A到B的最短路径（合理地说这应该称为最小步数）；

思路是：从图上的某个节点开始，访问首先访问其直连的子节点。如果子节点不匹配，则向子节点询问其子节点，并按级别顺序访问，直至到达目标节点。

所谓的“图”就是：

情况

如上图所示，找到从A到H的最短路径（步数最少的那条，假设每条距离相等），则您可以使用广域搜索算法，其原理步骤是：

1. 假设有一个空的搜索队列。队列，首先将节点A添加到队列中 队列
2. 判断队列中的第一个节点是否是要查找的目标节点，如果不是，则添加第三个节点 将某个节点的直接子节点添加到队列中，将第一个节点添加到队列中节点被移除
3. 重复评估，直到第一个节点为目标节点或队列为空（即没有匹配）

如下图所示 显示：

过滤搜索到的节点

对于已经搜索到的节点，最好存储其唯一的ID标识。如果后续搜索过程中再次出现该节点，则跳过搜索，不再重复搜索。提高效率，避免无限循环；

java实现

public class BFS {
    
    	public static void main(String[] args){
    		//初始化先建立起各个节点信息，以及对应的直接子节点列表
    		HashMap<String,String[]> map = new HashMap<>();
    		map.put("A", new String[] {"B","C"});
    		map.put("B", new String[] {"E"});
    		map.put("C", new String[] {"D","F"});
    		map.put("D", new String[] {"E"});
    		map.put("E", new String[] {"H"});
    		map.put("F", new String[] {"E","G"});
    		map.put("G", new String[] {"H"});
    		map.put("H", new String[] {});
    		//获取从A到H的最短路径节点链表
    		Node target = findTarget("A","H",map);
    		//打印出最短路径的各个节点信息
    		printSearPath(target);
    
    	}
    
    	/**
    	 * 打印出到达节点target所经过的各个节点信息
    	 * @param target
    	 */
    	static void printSearPath(Node target) {
    		if (target != null) {
    			System.out.print("找到了目标节点:" + target.id + "\n");
    			
    			List<Node> searchPath = new ArrayList<Node>();
    			searchPath.add(target);
    			Node node = target.parent;
    			while(node!=null) {
    				searchPath.add(node);
    				node = node.parent;
    			}
    			String path = "";
    			for(int i=searchPath.size()-1;i>=0;i--) {
    				path += searchPath.get(i).id;
    				if(i!=0) {
    					path += "-->";
    				}
    			}
    			System.out.print("步数最短："+path);
    		} else {
    			System.out.print("未找到了目标节点");
    		}
    	}
    	
    	/**
    	 * 从指定的开始节点 startId ，查询到目标节点targetId 的最短路径
    	 * @param startId
    	 * @param targetId
    	 * @param map
    	 * @return
    	 */
    	static Node findTarget(String startId,String targetId,HashMap<String,String[]> map) {
    		List<String> hasSearchList = new ArrayList<String>();
    		LinkedList<Node> queue = new LinkedList<Node>();
    		queue.offer(new Node(startId,null));
    		while(!queue.isEmpty()) {
    			Node node = queue.poll();
    			
    			if(hasSearchList.contains(node.id)) {
    				//跳过已经搜索过的，避免重复或者死循环
    				continue;
    			}
    			System.out.print("判断节点:" + node.id +"\n");
    			if (targetId.equals(node.id)) {
    				return node;
    			}
    			hasSearchList.add(node.id);
    			if (map.get(node.id) != null && map.get(node.id).length > 0) {
    				for (String childId : map.get(node.id)) {
    					queue.offer(new Node(childId,node));
    				}
    			}
    		}
    
    		return null;
    	}
    	
    	/**
    	 * 节点对象
    	 * @author Administrator
    	 *
    	 */
    	static class Node{
    		//节点唯一id
    		public String id;
    		//该节点的直接父节点
    		public Node parent;
    		//该节点的直接子节点
    		public List<Node> childs = new ArrayList<Node>();
    		public Node(String id,Node parent) {
    			this.id = id;
    			this.parent = parent;
    		}
    	}
    
    }
复制代码

执行main方法后，打印信息如下：

判断节点:A
    判断节点:B
    判断节点:C
    判断节点:E
    判断节点:D
    判断节点:F
    判断节点:H
    找到了目标节点:H
    步数最短：A-->B-->E-->H

作者：CodeInfo
链接：https://juejin.im/post/5b6464150d1950d1950d来源：掘金
版权属于作者。商业转载请联系作者获取授权。非商业转载请注明出处。