图的每个节点上的 DFS
DFS on each node of the graph
假设在我的有向图 G = (V, E) 中，我的节点分配了特定的数字 n[v]。我想为每个顶点找到最高的 n[v]，即 max(n[v]) 表示从 G.
中每个顶点可达的节点的最大 n[v]
我们如何有效地解决这个问题？
我正在考虑每个节点上的 DFS 行，无需回溯和比较所有 'visited' 节点的 n[v] 并存储该路径的最大 n[v] 值。
但是，恐怕这可能不是有效的解决方案。
为什么你认为这是低效的？
如果你 运行 在所有源节点上进行 DFS（只出边而没有边进入的节点），你可以保证访问所有节点。
只有在访问了节点的所有 children.
后，您才可以轻松地将 max(n[v]) 存储在节点上
然后，如果您从另一个源开始到达一个已经有 max(n[v]) 的节点，您知道您不必继续探索该节点 children，因为该值是仅在您访问了所有 children.
后分配
您在 ~|E| 中执行此操作步骤（除非你有孤立的节点，我们的边缘没有）因为你将恰好通过每条边缘一次。
我想如果你想要超级准确，你会在 |E| 中这样做+ |小号| |S| 的步骤是图中源节点的数量。
这对我来说似乎非常有效。我不确定是否有可能在不至少检查每条边一次的情况下获得确定性答案。
编辑：
此外，我想如果您想更加完整，您可能需要 运行 一个 pre-step 检查所有 V 节点以确定哪些是源节点。然后 运行仅在源节点上启用 DFS。
所以总体来说如果是 |V| + |E| + |小号|步骤是 O(|V| + |E|)
假设在我的有向图 G = (V, E) 中，我的节点分配了特定的数字 n[v]。我想为每个顶点找到最高的 n[v]，即 max(n[v]) 表示从 G.
中每个顶点可达的节点的最大 n[v]
我们如何有效地解决这个问题？
我正在考虑每个节点上的 DFS 行，无需回溯和比较所有 'visited' 节点的 n[v] 并存储该路径的最大 n[v] 值。
但是，恐怕这可能不是有效的解决方案。
为什么你认为这是低效的？
如果你 运行 在所有源节点上进行 DFS（只出边而没有边进入的节点），你可以保证访问所有节点。
只有在访问了节点的所有 children.
后，您才可以轻松地将 max(n[v]) 存储在节点上然后，如果您从另一个源开始到达一个已经有 max(n[v]) 的节点，您知道您不必继续探索该节点 children，因为该值是仅在您访问了所有 children.
后分配您在 ~|E| 中执行此操作步骤（除非你有孤立的节点，我们的边缘没有）因为你将恰好通过每条边缘一次。
我想如果你想要超级准确，你会在 |E| 中这样做+ |小号| |S| 的步骤是图中源节点的数量。
这对我来说似乎非常有效。我不确定是否有可能在不至少检查每条边一次的情况下获得确定性答案。
编辑：
此外，我想如果您想更加完整，您可能需要 运行 一个 pre-step 检查所有 V 节点以确定哪些是源节点。然后 运行仅在源节点上启用 DFS。
所以总体来说如果是 |V| + |E| + |小号|步骤是 O(|V| + |E|)