广度优先还是深度优先

Question

There is a theory that says six degrees of seperations is the highest degree for people to be connected through a chain of acquaintances. (You know the Baker - Degree of seperation 1, the Baker knows someone you don't know - Degree of separation 2)

We have a list of People P, list A of corresponding acquaintances among these people, and a person x

We are trying to implement an algorithm to check if person x respects the six degrees of separations. It returns true if the distance from x to all other people in P is at most six, false otherwise.

We are tying to accomplish O(|P| + |A|) in the worst-case.

为了实现这个算法，我考虑过在邻接矩阵上实现一个邻接表来表示具有顶点 P 和边 A 的图 G，因为邻接矩阵会走O(n^2)遍历

现在我考虑过使用 BFS 或 DFS，但我似乎无法找到为什么另一个更适合这种情况的原因。 我想使用 BFS 或 DFS 将 x 的距离存储在数组 d 中，然后遍历数组 d 以查看是否有度数大于 6 .

DFS 和 BFS 具有相同的时间复杂度，但在大多数情况下，深度更好（更快？）找到大于 6 的第一个度数，而广度更好地排除所有度数 > 6同时

在 DFS 或 BFS 之后，我将遍历包含与人 x 和 return true 的距离的数组，如果没有条目 >6 和 false 当找到一个时。

使用 BFS，分离度总是在数组的末尾，这可能会导致更高的时间复杂度？

使用 DFS 时，分离度会随机散布在数组中，但在搜索早期分离度高于 6 的可能性更高。

我不知道在这里使用 DFS 或 BFS 对时间复杂度是否有任何影响。

Answer 1

BFS和DFS的时间复杂度是完全一样的。这两种方法都访问图形的所有连接顶点，因此在这两种情况下，您都有 O(V + E)，其中 V 是顶点数，E 是边数。

也就是说，有时一种算法优于另一种算法正是因为 顶点访问顺序 不同。例如，如果你要评估一个数学表达式，DFS 会更方便。

在您的情况下，BFS 可用于优化图形遍历，因为您可以简单地在所需的分离级别切断 BFS。所有具有所需（或更大）分离度的人都不会被标记为已访问。

用 DFS 实现同样的技巧会复杂得多，因为正如您敏锐地注意到的那样，DFS 首先获得图的 "to the bottom"，然后它递归地（或通过堆栈）向上返回逐级。

Answer 2

我相信你可以使用 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

查看更多