[数据结构与算法]算法图解学习笔记：广度优先搜索

图由节点和边组成，一个节点可能和多个节点相连，这些节点成为邻接

广度优先搜索回答两个问题：1是否存在A到B路径 2从A到B哪条路径最短

广度优先搜索从起点的邻接节点开始，搜索完毕后再搜索其邻接节点的邻接

队列queue可以实现广度优先搜索，队列类似栈，不允许随机访问，只支持两个操作：入队和出队。队列先进先出(FIFO)，栈后进先出(LIFO)。

以下代码为自己原创，由于书上没有java版代码

package chapter6;

import java.util.*;

public class BreadthFirstSearch {
	
	public static boolean isSeller (String name) {
		if (name.substring(name.length() - 1, name.length()).equals("m")) {
			return true;
		} else {
			return false;
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		//construct the graph
		Map<String, String[]> graph = new HashMap<String, String[]>();
		String[] myFriends = {"Bob", "Alice", "Claire"};
		String[] BobFriends = {"Anuj", "Peggy", "me"};
		String[] AliceFriends = {"Peggy", "me"};
		String[] ClaireFriends = {"Thom", "Jonny"};
		String[] AnujFriends = {"Bob"};
		String[] PeggyFriends = {"Bob", "Alice"};
		String[] JonnyFriends = {"Claire"};
		String[] ThomFriends = {"Claire"};
		graph.put("me", myFriends);
		graph.put("Bob", BobFriends);
		graph.put("Alice", AliceFriends);
		graph.put("Claire", ClaireFriends);
		graph.put("Anuj", AnujFriends);
		graph.put("Peggy", PeggyFriends);
		graph.put("Jonny", JonnyFriends);
		graph.put("Thom", ThomFriends);
		
		
		//search the graph
		Queue<String> searchLine = new LinkedList<String>();
		Set<String> searched = new HashSet<String>();
		searched.add("me");
		for (String i : graph.get("me")) {
			searchLine.add(i);
		}
		while (!searchLine.isEmpty()) {
			String friend = searchLine.poll();
			if (isSeller(friend)) {
				System.out.println("The mango seller with the closest relationship is " + friend);
				break;
			} else if (!searched.contains(friend)){
				searched.add(friend);
				System.out.println(friend + " is not a mango seller");
				String[] friends = graph.get(friend);
				if (friends != null) {
					for (String i : friends) {
						searchLine.add(i);
					}
				}
			}
		}
	}

}

使用一个散列表构建图（比数组好用），判断是芒果销售员（名字最后一个字母为m）的关系最近的朋友，队列实现广度优先搜索，同时用一个set记录已经搜索过的节点，不重复搜索节点非常重要，否则图中只要有一个环就会无限循环