算法图解-广度优先搜索-芒果销售商(Java实现)

芒果销售商问题

寻找芒果销售商的问题，由于书中使用的是Python语言，而我是搞Java的，这里用Java实现一下，大佬勿喷，小弟还是初学者，只是顺便记录下学习的过程。

废话不多说直接上代码

public class OtherTest {
    private Map<String, String[]> graph;
    private Set<String> serched;//存放访问过的人 防止重复
    private Queue<String> quen; //队列
	//构造函数
    public OtherTest(Map<String, String[]> map, String persion){	
        graph = map;
        serched = new HashSet<>();
        quen = new LinkedBlockingQueue<>();
        addQuen(persion);
    }
    
	/**
     * 添加队列
     * @param persion
     */
    private void addQuen(String persion) {
        String[] array = graph.get(persion);
        if(array.length>0) {
            for (String arr : array) {
                quen.offer(arr);//添加人名到队列
                serched.add(persion);//访问过的添加到集合 防止重复
            }
        }
    }

    public static void main(String[] args) {
        //散列函数 不知道什么是散列函数的去看看此书的前一章   时间复杂度O(1)
        Map<String, String[]> map = new HashMap<>();
        map.put("you", new String[]{"alice", "bob", "claire"});
        map.put("bob",new String[]{"anuj","peggy"});
        map.put("alice", new String[]{"peggy"});
        map.put("claire", new String[]{"thom", "jonny"});
        map.put("anuj", new String[]{});
        map.put("peggy", new String[]{});
        map.put("thom", new String[]{});
        map.put("jonny", new String[]{});

        OtherTest ot = new OtherTest(map, "you");
        System.out.println(ot.getSerch());
    }
	
    /**
     * 查找
     *
     * @return
     */
    private String getSerch() {
        while (quen != null) {
            String str = quen.poll();//获取队列的第一个值，并移除
            if (!serched.contains(str)) {
                if (serch(str)) {
                    return str + " is m";
                } else {
                    addQuen(str);
                }
            }
        }
        return "nobody is m";
    }


    public static boolean serch(String msg) {
        if (msg.equals("peggy")) { //这里可以随便设置谁是芒果商
            return true;
        } else {
            return false;
        }
    }
}

---

总结

主要用到了队列、散列函数。其他都是基础知识。

本文地址：https://blog.csdn.net/qq_35919852/article/details/111379586