这是我试图使用图算法解决的一个问题。如果熟悉不同的图遍历算法，这个问题的答案很容易。我想了解的是如何降低这个问题的复杂度？
假设我们必须遍历某人的网络 - 朋友、朋友 朋友 (FoF) 和 FoFoF（1 级、2 级、3 级.. 直至 6 级） 搜索特定的事物，例如“居住在加利福尼亚州的人”。这 当你有 1000 个朋友时，问题的复杂性就会大大增加 你的 1000 个朋友各有 1000 个朋友，依此类推。
假设我们想要进行优化搜索，您知道 目的地节点（这里是居住在加利福尼亚州的人）。
你会怎样 降低问题的复杂性？您提交的程序应返回该人的学位 与您相连。 [其中“目标节点”是您的第 1 度 （朋友），或第二（朋友的朋友）或第三学位（FoFoF）或学位 大于 3 度]。
假设您的图未加权，执行广度优先搜索将为您提供最短路径（这实际上是您需要的度数）。如果目的地已知，您还可以使用 Dijkstra 算法来查找到该特定节点的最短路径，但如果图未加权，则仅执行 BFS 会更有效，因为它的复杂性低于 Dijkstra 算法。另外，如果我理解正确的话，你的输出必须只涵盖 4 种情况：1、2、3 度或更高。如果是这样，您可以只对前三个级别进行 BFS 并存储结果。然后你可以通过检查 BFS 获得的数据中是否存在这样的人来在常数时间内回答问题。