中等
技术面试0 次浏览

微博的用户关系图是一个复杂的网络,现在要设计一个算法,计算两个用户之间的最短关系路径。假设用户关系图用邻接表表示。

微博算法工程师
图算法最短路径Python

答题要点

本题可使用广度优先搜索(BFS)算法来解决,答题框架遵循 BFS 的基本流程。关键要点如下:1. 初始化队列,将起始用户加入队列,并记录其距离为 0。2. 进行 BFS 搜索,不断从队列中取出用户,检查其邻居节点。3. 若邻居节点未被访问过,更新其距离并加入队列。4. 当找到目标用户时,返回最短路径长度。示例思路:首先,创建一个队列并将起始用户加入,同时记录其距离为 0。然后,在队列不为空时,取出队首用户,遍历其邻居节点。若邻居节点未被访问,将其加入队列并更新距离。当遇到目标用户时,返回其距离。