BFS:广度优先搜索

恭喜发现宝藏！微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。 作者@TechGuide【全网同名】 点赞再看，养成习惯，您动动手指对原创作者意义非凡🤝

前言

在笔者大大小小笔试了五六场之后，似乎得到了一点规律，互联网大厂的笔试题集中在两大块，一是dp动态规划，另外一个就是dfs深度优先搜索（也包含回溯问题）了（此处再补充一个——BFS 广度优先搜索）。之前笔试的时候，总是觉得面对这种类型的题目，即使勉强写出来了，也远远没有达到融会贯通的程度，很是苦恼。看了几十篇高赞高评论的总结对比文章后，并没有觉得有什么帮助，我总结了两个原因，第一个原因就是作者讲的太浅了，最然容易理解，却无法实际运用到更加复杂的场景中，另一个原因就是，很多别人得出的宝贵结论，你因为缺少自己的思考和大量题目的训练而无法感同身受，因而无法体会到其中的精妙之处。这里我专门讲一下leetcode中的BFS专题下的题目，试一试能不能总结出一些规律，也给自己练习用。

本文末尾附上了图论的几个经典算法，供感兴趣的读者拓展延伸。

正文 Leetcode127. word Ladder

思路： 利用两个set分别从beginword和endword层序替换成新的一批wordset，直到两个set互相有联通了，返回链长度；或者某个set为空时，返回0.这里用了双向BFS，会调换beginset和endset

public int ladderLength(String beginWord, String endWord, List wordList) {
        Set wordSet = new HashSet(wordList);
        if(!wordSet.contains(endWord)) return 0;
        Set beginSet = new HashSet(), endSet = new HashSet();
        beginSet.add(beginWord);
        endSet.add(endWord);
        int len = 1;
        Set vis = new HashSet();

        while(!beginSet.isEmpty()&&!endSet.isEmpty()){
            if(beginSet.size()>endSet.size()){
                Set temp = beginSet;
                beginSet = endSet;
                endSet = temp;
            }

            Set temp = new HashSet();
            for(String word:beginSet){
                char[] chars = word.toCharArray();
                for (int i = 0; i  "0001" -> "0002" -> "0102" -> "0202" would
// be invalid,
//because the wheels of the lock become stuck after the display becomes the dead
// end "0102".
// 
//
// Example 2: 
//
// 
//Input: deadends = ["8888"], target = "0009"
//Output: 1
//Explanation:
//We can turn the last wheel in reverse to move from "0000" -> "0009".
// 
//
// Example 3: 
//
// 
//Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], t
//arget = "8888"
//Output: -1
//Explanation:
//We can't reach the target without getting stuck.
// 
//
// Example 4: 
//
// 
//Input: deadends = ["0000"], target = "8888"
//Output: -1
// 
//
// 
// Constraints: 
//
// 
// 1