Introduction of algorithm

Breadth First Search algorithm, also known as “Breadth First Search” or “horizontal First Search”, referred to as BFS; BFS is a search algorithm for graphs (requiring graphs to represent the relevance of problems).

BFS can be used to solve two types of problems:

  • Whether there is A path from A to B;
  • The shortest path from A to B (this should be called the least reasonable step);

The idea is to start from a node on the graph and visit the directly connected child node first. If the child node does not match, the child node of the child node is asked, and then visit in sequence according to the level until the target node is accessed.

The so-called “figure” is:

case

As shown in the figure above, find the shortest path from A to H (with the least steps, assuming that each distance is equal), then wide-area search algorithm can be used. The principle steps are as follows:

  1. Suppose there is an empty search Queue, first add node A to Queue
  2. Determine whether the first node in the queue is the target node to look for. If not, add the direct child node of the first node to the queue and remove the first node
  3. Repeat the judgment until either the first node is the target node or the queue is empty (meaning there is no suitable one)

As shown below:

Filter the nodes that have already been searched

It is better to save the unique ID of the node that has been searched. If the node appears again in the subsequent search, the search will be skipped and not repeated to improve efficiency and avoid endless cycles.

Java implementation

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[] {}); Node target = findTarget("A"."H",map); // Prints information about each node of the shortest pathprintSearPath(target); } @param target */ static voidprintSearPath(Node target) {
    		if(target ! = null) { System.out.print("Target node found :" + 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("Shortest steps:"+path);
    		} else {
    			System.out.print("Target node not found"); } /** * Query the shortest path of the target node targetId * @param startId * @param targetId * @param map * @ from the specified start node startIdreturn
    	 */
    	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)) {// Skip already searched items to avoid repetition or endless loopscontinue;
    			}
    			System.out.print("Judge node :" + 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)); }}}returnnull; } /** * nodeObject * @author Administrator ** / static class Node{// nodeid public String id; // The immediate parent of this Node is public Node parent; Public List<Node> childs = new ArrayList<Node>(); public Node(String id,Node parent) { this.id = id; this.parent = parent; }}}Copy the code

The following information is displayed after the main method is executed:

Judge node :A Judge node :B judge node :C Judge node :E Judge node :D Judge node :F Judge node :H Find the target node :H The shortest steps :A -->B-->E-->HCopy the code

Scan and follow wechat official account: