深度优先搜索——遍历随机邻居的优势
Depth First Search - Advantages of traversing random neighbours
深度优先搜索允许以任意顺序遍历相邻顶点。
选择随机邻居与选择升序邻居有什么优势吗？
考虑下图的探索顺序：
0 -> 9 -> 8 -> 7 ..
0 -> 1 -> 8 -> 7 ..
随机选择能否带来更有利的结果？
首先，乱序DFS不负责
遍历节点的方式取决于两件事：
在邻接列表中推送相邻节点的顺序（通常受输入中提供的边的顺序影响）。
您决定遍历的自定义顺序（如您所述，排序顺序）。
你问题的答案：
选择在邻接列表中推送相邻节点的顺序不会影响复杂性。
如果决定按排序遍历相邻节点，则需要相应地维护邻接表，这是以额外的因子V*log(V)为代价的。
总时间复杂度 = O(V+E) + O(V * log(V))。
O(V+E) => 对于 DFS。
O(V * log(V)) => 优先级 queue/sorting 邻接表。
此处，V = 图中的节点数，E = 边数。
我能找到有优势的情况吗？
是的。容易地。如果我有一个连通图，随机选择的遍历保证最终到达每个节点。按顺序遍历最终会陷入循环。
总的来说有优势吗？
没有。例如在连接的例子中，一个简单的“跟踪我们去过的地方”就可以让两者都达到一切。哪一个最先找到目标节点将是一个机会问题。
深度优先搜索允许以任意顺序遍历相邻顶点。 选择随机邻居与选择升序邻居有什么优势吗？
考虑下图的探索顺序：
0 -> 9 -> 8 -> 7 ..
0 -> 1 -> 8 -> 7 ..
随机选择能否带来更有利的结果？
首先，乱序DFS不负责
遍历节点的方式取决于两件事：
在邻接列表中推送相邻节点的顺序（通常受输入中提供的边的顺序影响）。
您决定遍历的自定义顺序（如您所述，排序顺序）。
你问题的答案：
选择在邻接列表中推送相邻节点的顺序不会影响复杂性。
如果决定按排序遍历相邻节点，则需要相应地维护邻接表，这是以额外的因子V*log(V)为代价的。
总时间复杂度 = O(V+E) + O(V * log(V))。
O(V+E) => 对于 DFS。
O(V * log(V)) => 优先级 queue/sorting 邻接表。
此处，V = 图中的节点数，E = 边数。
我能找到有优势的情况吗？
是的。容易地。如果我有一个连通图，随机选择的遍历保证最终到达每个节点。按顺序遍历最终会陷入循环。
总的来说有优势吗？
没有。例如在连接的例子中，一个简单的“跟踪我们去过的地方”就可以让两者都达到一切。哪一个最先找到目标节点将是一个机会问题。