BFS算法与一次踩坑记录

本文最后更新于：2023年12月17日下午

前言

最近在练习BFS算法，在leecode上刷到这样一道题 752. 打开转盘锁 - 力扣（LeetCode），其实题目本身的解法思路还是很清晰的，但是没有注重好细节，导致踩了个坑，在debug排查时更是遇到了出乎意料的错误，所以写下这篇文章吸取教训。

解题思路

题目大意就是给定固定长度为4的字符串”0000”，每次只能改变其中一个字符，并且一次只能加1或者减1（比如 ‘0’ ->’9’ 或 ‘9’->’0’），并且给出一个字符串数组 deadends，改变之后的字符串不能再

deadends数组中，问最少需要多少次改变能变成目标字符串target。

解题思路的话就是BFS搜索，把每个字符串看做一个节点/状态，每次改变之后变成一个新的节点/状态，而从一个状态转变为另一个状态，有 4 * 2 个选择（4位置，2种变法），然后判断该状态是否为最终目标状态，使用BFS搜索就可以求得最少次数的转变。下面给出具体实现代码。

普通BFS搜索版本1

int openLock(vector<string>& deadends, string target) {
    unordered_set<string> s;
    for (string& str : deadends) {
        s.insert(str);
    }
    string start = "0000";
    if (s.count(start) > 0) {
        return -1;
    }
    int ans = 0;
    queue<string> q;
    q.push(start);
    s.insert(start);
    while (!q.empty()) {
        int size = q.size();
        for (int i=0; i < size; i++) {
            start = q.front();
            q.pop();
            if (start == target) {
                return ans;
            }
            for (int j=0;j<4;j++) {
                string next = start;
                next[j] = (start[j] - '0' + 1) % 10 + '0';
                if (s.count(next) == 0) {
                    s.insert(next);
                    q.push(next);
                }
                next[j] = (start[j] - '0' + 9) % 10 + '0';
                if (s.count(next) == 0) {
                    s.insert(next);
                    q.push(next);
                }
            }
        }
        ans++;
    }

    return -1;
}

普通BFS搜索版本2

int openLock(vector<string>& deadends, string target) {
    unordered_set<string> s;
    for (string& str : deadends) {
        s.insert(str);
    }
    string start = "0000";
    if (s.count(start) > 0) {
        return -1;
    }
    int ans = 0;
    queue<string> q;
    q.push(start);
    while (!q.empty()) {
        int size = q.size();
        for (int i=0; i < size; i++) {
            start = q.front();
            q.pop();
            if (start == target) {
                return ans;
            }
            if (s.count(start) > 0 ) {
                continue;
            }
            s.insert(start);
            
            for (int j=0;j<4;j++) {
                string next = start;
                next[j] = (start[j] - '0' + 1) % 10 + '0';
                if (s.count(next) == 0) {
                    q.push(next);
                }
                next[j] = (start[j] - '0' + 9) % 10 + '0';
                if (s.count(next) == 0) {
                    q.push(next);
                }
            }
        }
        ans++;
    }

    return -1;
}

BFS搜索实现比较

下面来分析下上述两个版本实现的区别。左图是版本1的写法，右图是版本2的写法，可以观察到两者的区别在于 s 集合（也就是已访问节点的集合）插入的位置或者说时机不同。（对于版本1来说，还需要在进入队列循环前把起始节点加入到访问集合中）

左图的做法是放入队列的同时就插入集合，认为该节点已访问，所以在外层循环真正取出的时候不用再进行判断和插入；而右图的做法是当节点从队列中取出的时候，才认为该节点被访问再进行插入，那么此时插入集合前判断该节点此前以是否已经访问的 if 语句就是必须的。因为把节点加入队列的时候没有进行判断去重，那么在同一层level 上，是会存在两个节点的状态相同的情况，比如(0000->1000->2000->3000->4000->5000 ，与 0000->9000->8000->7000->6000->5000 这两条路径的长度都是5，所以最终节点会在同一层上，也都会被加入到队列中。如果从队列中取出的时候不进行判断是否已经访问，那么就会去重复搜索这两个相同节点的路径，导致耗时指数增加，而这部分搜索本该是需要被剪枝的。

而我当时就是没有想清楚这里的逻辑，一头栽进这个坑里，也才有了这篇文章（doge）。

双向BFS优化

这里再提一下BFS还有一个高级的优化方法：双向BFS。参考 BFS 算法解题套路框架 :: labuladong的算法小抄^[1]。

传统的 BFS 框架就是从起点开始向四周扩散，遇到终点时停止；而双向 BFS 则是从起点和终点同时开始扩散，当两边有交集的时候停止。

从时间复杂度分析的话，虽然双向BFS会有一定的优化，但和普通BFS一样，其最坏复杂度都是 O(N)。并且双向 BFS 也有局限，那就是你必须要知道最终的节点位置或者说最终的状态是怎样的。

下面给出了使用双向BFS的实现。

// 双向BFS
int openLock(vector<string>& deadends, string target) {
    unordered_set<string> visited;
    for (string& str : deadends) {
        visited.insert(str);
    }
    unordered_set<string> start;
    unordered_set<string> end;
    start.insert("0000");
    end.insert(target);
    if (visited.count("0000") > 0) {
        return -1;
    }
    int ans = 0;

    while (!start.empty() && !end.empty()) {
        unordered_set<string> next_level;

        for (const string& str : start) {
            if (end.count(str) > 0) {
                return ans;
            }
            if (visited.count(str) > 0) {
                continue;
            }
            visited.insert(str);
            
            for (int j=0;j<4;j++) {
                string next = str;
                next[j] = (str[j] - '0' + 1) % 10 + '0';
                if (visited.count(next) == 0) {
                    next_level.insert(next);
                }
                next[j] = (str[j] - '0' + 9) % 10 + '0';
                if (visited.count(next) == 0) {
                    next_level.insert(next);
                }
            }
        }
        ans++;
        start = end;
        end = next_level;
    }

    return -1;
}

踩坑记录

接下来再具体谈谈我踩的坑吧，上文提到了两个普通BFS搜索实现的区别，而我当时采用的就是版本2的写法，并且没有写判断是否已访问的逻辑，因此造成结果不符合预期。所以我使用CLion进行debug排查，但是在debug过程，遇到了下面这个离奇的现象。

可以看到，在debug模式下，明明队列q里已经没有元素了，显示的q.size也为0，但是赋值得到的 size 却不为0。当时真的是百思不得其解，整个人有点小懵，然后加各种打点去看，但发现明明队列里就是有值，可显示的却是0。因为我当时还是认为程序逻辑没有错，认为这里队列就应该是空，所以一直认为是不是其他哪里有问题。

直到后来无计可施了，我才开始重新梳理逻辑，确定逻辑上这里的队列是否有值，然后就发现是代码逻辑本身有问题。这样一来，问题就明朗许多了，开始考虑是不是编译器或者调试工具的问题。

后来发现的确是编译器显示的问题，在CLion里，当队列里的元素个数超过255时，只会显示255或者为0，在vscode里进行测试时也同样有这个问题。不过vscode好像是会一直保持size=255。

CLion调试1

CLion调试2

CLion调试3

VsCode调试1

VsCode调试2

之后又在CLion上测试了vector，list，set，deque，stack，map，发现只有deque、queue、stack会出现显示的size和真实size不一致的情况，不难猜想根源在于deque，因为queue和stack底层默认采用deque实现。那么为什么会出现这样的情况呢？程序逻辑是正常的，那么只可能是IDE显示或者调试工具的问题了，或许是因为deque底层数据结构比较复杂，当元素数量大起来之后，调试工具难以追踪导致显示不一致吧。

在stackoverflow上也找到一个类似的问题，跟猜想大体一致：https://stackoverflow.com/questions/53972627/deque-not-growing-larger-than-255-elements ^[2]

总结

总的来说，这次踩坑的教训就是，一定要先仔细、慎重地思考好代码逻辑，认为实在看不出问题来了再去debug调试（好像说了句废话。。。），大意就是不要太依靠调试工具，或者说先把一些基本逻辑理清，确定一些前提条件后再去排查问题，会更有效率，就比如这次如果我能理清逻辑的话，能确定队列大小的size不为0，那就能更快地进行排查测试，而不是在哪里纠结，往错误的方向上思考了。

正所谓方向错了，所做的努力都是徒劳。

草上飞2