完善了一下这两个预留的方法
private static boolean hasOverlap(HashSet<Integer> visited_a, HashSet<Integer> visited_b) {
        if (visited_a.isEmpty() || visited_b.isEmpty())
            return false;
        for (int user_id_a : visited_a) {
            if (visited_b.contains(user_id_a)) {
                return true;
            }
        }
        return false;
    }

    private static void getNextDegreeFriend(int user_id_a, Node[] user_nodes, Queue<Integer> queue_a,
            HashSet<Integer> visited_a, int degree_a) {
        if (user_nodes[user_id_a] == null)
            return;
        Node current_node = user_nodes[user_id_a];
        HashSet<Integer> friends = current_node.friends;
        if (friends.isEmpty())
            return;
        HashMap<Integer, Integer> degrees = current_node.degrees;
        for (int f_user_id : friends) {
            queue_a.offer(f_user_id);
            visited_a.add(f_user_id);
            degrees.put(f_user_id, degree_a + 1);
        }
    }
        // 初始化节点数组
    public static Node[] init(int user_num, int relation_num) {
        Random rand = new Random();
        Node[] user_nodes = new Node[user_num];

        // 生成所有表示用户的节点
        for (int i = 0; i < user_num; i++) {
            user_nodes[i] = new Node(i);
        }

        // 生成所有表示好友关系的边
        for (int i = 0; i < relation_num; i++) {
            int friend_a_id = rand.nextInt(user_num);
            int friend_b_id = rand.nextInt(user_num);
            if (friend_a_id == friend_b_id)
                continue;
            Node friend_a = user_nodes[friend_a_id];
            Node friend_b = user_nodes[friend_b_id];
            friend_a.friends.add(friend_b_id);
            friend_b.friends.add(friend_a_id);
        }

        return user_nodes;
    }
        // 测试
    public static void main(String[] args) {
        Node[] user_nodes = init(5, 8);
        for (Node d : user_nodes) {
            System.out.println(d.user_id + ":" + d.friends + ":" + d.degrees);
        }
        System.out.println("-----------------");
        int len = bi_bfs(user_nodes, 0, 1);
        System.out.println("距离：" + len);
    }
运行结果：
0:[2, 3, 4]:{0=0}
1:[2, 4]:{1=0}
2:[0, 1]:{2=0}
3:[0]:{3=0}
4:[0, 1]:{4=0}
-----------------
距离：2

老师您帮忙看下程序逻辑有没有什么问题，从测试结果来看应该是对的。

思考题：能想到的是当 a b 结点的好友数量极度不对称时，单向更快；优化思路是，每一次迭代时比较下一层结点的数量，若是两边的数量级有明显差距（设置个阈值），则优先选择数量级小的一边进行搜索。但这样的做的弊端也很明显——很可能这一边不断往下搜索，但事实上另一边只要往下一层就完事了。所以还需要限制单边【连续优先搜索】的次数。

提问：老师，您有开头提到需要对 Node 添加一个 degrees 的 HashMap 变量来纪录其他用户结点与 self 的距离，但是后边用到的外部变量 degree_a 事实上就代替了这个功能是吗？
另外在实际应用中 max_degree 是设置为树的高度吗，还是可以有其他优化方式？

"双向广度优先比单向广度优先更高效"的前提条件是"两个被搜索的节点必须是联通的"如果不是联通的，两个节点都会将他们各自的N度好友都找出来，不如只搜索其中一个；
针对这种情况可以维护一个网络分块信息表，每当有连接加入这个网络时检查一下它是否将两个分割的块连接起来了，如果是将这两个块标记为同一个块。在查找的时候就方便了，如果两个节点本身就不在一个块里面，距离直接就是无穷远。但是如果这个网络里面的连接还能删除的话就比较麻烦了，每删除一条边还要检查是否将一个块分割成了两个块，计算量比较大。

深度优先搜索占用空间少，但是速度比较慢；广度优先搜索占用空间多，但是运行速度快，属于空间换时间吧。进一步，双向广度优先搜索，似乎也是用了更多的空间，来换取搜索效率。

对于后来那个聚类的例子，我有点不理解，感觉更多的时采用了剪枝的思路，和双向广度优先搜索好像没什么关系，当然也可以说是把之前的深度优先搜索，改为了广度优先同时剪枝。

对于思考题，在需要列举全部好友关系的情况下，以及在树的分叉比较多的情况下，似乎单向广度优先搜索的效率更高，主要是因为减少了比对的复杂性。

看了一下回复里面的答案，说是在 a 和 b 好友分布不均匀的情况下，从好友少的一段开始单向广度搜索，效果更好。

学习了 @菩提 的 Java 代码 和 @qinggeouye 的 Python 代码

在数学课里面看到关于用数据结构表达树，还是感觉有点奇怪，不过作者给出的 TreeNode 应该算是比较经典的一种，学习了。我觉的前缀树里面 prefix 和 label 的设计，很有想法，可以很方便的做前缀树的搜索，以前可能是忽略了这一部分。

使用 TreeNode 和 Stack 实现深度优先搜索，还是比较巧妙的，虽然也许递归的写法看上去会更简单一些。

使用临时栈来保证子节点的访问顺序和递归遍历时的访问顺序一致，也是一个比较有意思的地方。

自己用代码实现比较困难，所以还是学习了留言中的代码，其中 @qinggeouye 的 Python 代码最为漂亮，感谢。

如果在图中进行深度优先搜索，一个是要记录走过的节点，另外一个就是可能没有办法保障第一次就走完最长的路线，因为所有的点都是平级的，没有父子关系。所以，对图来说，是不是没有深度优先和广度优先的说法，只有遍历而已。

https://github.com/qinggeouye/GeekTime/blob/master/MathematicProgrammer/14_breadthFirstSearch/lesson14_1.py

两个预留方法的 python 实现：

get_next_degree_friend(user_nodes, que, visited) 去掉了 user_id_a 和 degree_a 两个参数。
如果把 user_id_a 看作圆心，它的一度好友看作第一层节点，二度好友看作第二层节点 .... ，que 队列只保留某一层的节点即可，visited 仍保存所有访问过的节点。

def get_next_degree_friend(user_nodes, que, visited):
    """
    :param user_nodes: 用户节点网络
    :param que: 某一层用户节点 即第几度好友
    :param visited: 已访问的所有用户节点
    :return:
    """
    que_return = queue.Queue() # 只保存某个用户的第几度好友
    visited_return = set() # 保存从某个用户开始到第几度好友
    while not que.empty():
        current_user_id = que.get()
        if user_nodes[current_user_id] is None:
            continue
        for friend_id in user_nodes[current_user_id].friends:
            if user_nodes[friend_id] is None:
                continue
            if friend_id in visited:
                continue
            que_return.put(friend_id)
            visited_return.add(friend_id) # 记录已经访问过的节点
    return que_return, visited_return

def has_overlap(visited_a, visited_b):
    # 两个 set() 的交集
    return len(visited_a & visited_b) > 0

#测试结果：
if __name__ == "__main__":
    user_nodes_list = set_user_relation(10, 20)
    for i in range(len(user_nodes_list)):
        print("用户 %s 的好友: %s" % (user_nodes_list[i].user_id, user_nodes_list[i].friends))
    print("---------双向广度优先搜索---------")
    print("两个用户节点 1和2 之间的最短路径长度：", bi_bfs(user_nodes_list, 1, 2))

用户 0 的好友: {8, 2, 3, 6}
用户 1 的好友: {8, 3, 5}
用户 2 的好友: {0, 4}
用户 3 的好友: {0, 1, 4, 5, 8, 9}
用户 4 的好友: {2, 3}
用户 5 的好友: {9, 3, 6, 1}
用户 6 的好友: {0, 8, 5}
用户 7 的好友: {9}
用户 8 的好友: {0, 1, 3, 6, 9}
用户 9 的好友: {8, 3, 5, 7}
---------双向广度优先搜索---------
两个用户节点 1和2 之间的最短路径长度： 3