DFS 关于无向图的复杂性？
DFS on undirected graph complexity?
当我们使用 DFS 遍历无向连通图并仅标记出我们在 DFS 期间遍历的边时，我们最终得到一个 DFS 树，它基本上是一棵树并遍历一棵树需要 O(v) 复杂度，其中 v 是顶点数，那么为什么说复杂度是 O(v + e)？
我知道这是一个菜鸟问题，但我很困惑。
你通过边找到图的所有节点，所以时间复杂度取决于否。这也是为什么 O(e) 也包括在内的原因。如果你认为完整的图 TC 将是 O(V^2).
考虑两个不同的图表：
边数多于顶点数的图，例如 connected graph with a high minimum degree.
当DFS算法访问一个顶点时，它必须沿着连接该顶点的每条边，从相邻的顶点重复一次DFS遍历。当然，如果那个邻居已经被访问过，DFS 算法会回溯，但至少我们可以声明必须处理该边。
此过程将处理图的所有 条边。所以在这种情况下我们可以说算法是 O(e)
边比顶点少的图，通常是不连通的图（在极端情况下没有边）。
当 DFS 算法已经访问了从顶点 A 开始的遍历可以到达的所有顶点时，它仍然必须迭代剩余的顶点，以找到可能没有被访问过的顶点。这些未访问的顶点不属于同一个 connected component)。另一个DFS遍历必须从那里开始。
这样所有个顶点都被处理了。所以在这种情况下，算法具有 O(v) 时间复杂度
所以一般来说，算法的时间复杂度是O(max(e, v))。您也可以说该算法必须访问所有边 和 所有顶点，因此该算法具有 O(e+v) 时间复杂度。两者是等价的。
DFS 树是由您遍历 的边组成的树。您确实只遍历 O(V) 条边。但是为了遍历一条边，您首先要检查 这条边以检查它是否会通向您已经遇到的顶点。这意味着您 检查的边比您遍历的边多。实际上，您检查了 O(E) 个边。所以总工作量是 O(V+E).
注：因为你的图是连通的，你确定E > V。在那种情况下，复杂度可以改写为 O(E).
当我们使用 DFS 遍历无向连通图并仅标记出我们在 DFS 期间遍历的边时，我们最终得到一个 DFS 树，它基本上是一棵树并遍历一棵树需要 O(v) 复杂度，其中 v 是顶点数，那么为什么说复杂度是 O(v + e)？
我知道这是一个菜鸟问题，但我很困惑。
你通过边找到图的所有节点，所以时间复杂度取决于否。这也是为什么 O(e) 也包括在内的原因。如果你认为完整的图 TC 将是 O(V^2).
考虑两个不同的图表：
边数多于顶点数的图，例如 connected graph with a high minimum degree.
当DFS算法访问一个顶点时，它必须沿着连接该顶点的每条边，从相邻的顶点重复一次DFS遍历。当然，如果那个邻居已经被访问过，DFS 算法会回溯，但至少我们可以声明必须处理该边。
此过程将处理图的所有 条边。所以在这种情况下我们可以说算法是 O(e)
边比顶点少的图，通常是不连通的图（在极端情况下没有边）。
当 DFS 算法已经访问了从顶点 A 开始的遍历可以到达的所有顶点时，它仍然必须迭代剩余的顶点，以找到可能没有被访问过的顶点。这些未访问的顶点不属于同一个 connected component)。另一个DFS遍历必须从那里开始。
这样所有个顶点都被处理了。所以在这种情况下，算法具有 O(v) 时间复杂度
所以一般来说，算法的时间复杂度是O(max(e, v))。您也可以说该算法必须访问所有边 和 所有顶点，因此该算法具有 O(e+v) 时间复杂度。两者是等价的。
DFS 树是由您遍历 的边组成的树。您确实只遍历 O(V) 条边。但是为了遍历一条边，您首先要检查 这条边以检查它是否会通向您已经遇到的顶点。这意味着您 检查的边比您遍历的边多。实际上，您检查了 O(E) 个边。所以总工作量是 O(V+E).
注：因为你的图是连通的，你确定E > V。在那种情况下，复杂度可以改写为 O(E).