有一种理论认为六度的分离是最高的 通过一连串熟人将人们联系起来。 (你知道贝克 - 分离程度
1，贝克认识某人 你不知道 - 分离程度2(我们有一个人员列表
P，列出A相应的熟人 在这些人中，有一个人x我们正在尝试实现一种算法来检查
x是否尊重 六度分离。true如果距离x对P中的所有其他人来说，最多是六个，否则是错误的。我们将在最坏的情况下完成
O(|P| + |A|)。
为了实现这个算法，我想过在邻接矩阵上实现一个邻接列表，以表示顶点P和边A的图G，因为邻接矩阵需要O(n^2)才能遍历。
现在我想过使用 BFS 或 DFS，但我似乎找不到为什么另一个更适合这种情况的原因。 我想使用 BFS 或 DFS 将x的距离存储在数组d中，然后在数组d上循环查看是否有任何度数大于6度。
DFS和BFS具有相同的时间复杂度，但在大多数情况下，深度在查找大于6的第一度时更好(更快？(，而广度在同时排除所有度数时更好> 6。
在DFS或BFS之后，我将遍历包含与人x距离的数组，如果没有条目>6则返回true，并在找到条目时返回false。
对于BFS，分离度总是在数组的末尾，这可能会导致更高的时间复杂度？
使用 DFS，分离度将随机分散在阵列中，但在搜索早期分离度高于6的几率更高。
我不知道如果在这里使用 DFS 或 BFS，它是否会对时间复杂度有任何影响。
BFS和DFS的时间复杂度完全相同。这两种方法都访问图的所有连接顶点，因此在这两种情况下您都有O(V + E)，其中V是顶点数，E是边数。
话虽如此，有时一种算法可以优于另一种算法，正是因为顶点访问的顺序不同。例如，如果您要计算数学表达式，DFS 会方便得多。
在您的情况下，BFS 可用于优化图形遍历，因为您可以简单地在所需的分离级别切断 BFS。所有具有所需(或更大(分离程度的人都将不被标记为被访问。
同样的技巧在DFS中实现起来会更加复杂，因为正如你敏锐地注意到的那样，DFS首先到达图形的"底部"，然后递归地(或通过堆栈(逐级返回。
我相信你可以使用Dijkstra算法。
是更新路径的BFS方法，是路径具有较小的值。想想距离总是要付出1，如果你有两个朋友(A和B(一个人N。
这些朋友有一个共同的朋友C但是，在第一次你的算法检查朋友的距离时，A成本4并标记为访问过，他们无法检查可能3距离的朋友B。Dijkstra将帮助您检查这一点。
Dijkstra在O(|V|+|E|log|V)解决了这个问题
在 https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm 查看更多信息