问题:
有向图和无向图的 DFS 复杂性是否不同?
如果是,那么有向图复杂度为 O(V + E),无向图复杂度为 O(E) ?其中 E 是边,V 是顶点?
如果是,则以下注释 - 有向图的 O(V+E) 复杂度的解释是否正确?
/*
* Although this piece looks like it is O(V * E), it is actually O(V + E)
* This is because, for each node, we dont do dfs across the full tree.
* ie
* A -> C
* |
* V
* B
* Here A has a directed edge to B and C.
* This means that when 'Node' == A then 'dfs' code would cost O(E)
* But when the 'node' == B then 'dfs' would cost O(1), since B does not have any outgoing edge
* and when the 'node' == C then 'dfs' would cost O(1), since C does not have any outgoing edge
* This O(E + 1 + 1) = O(E)
* And O(A + B + C) = O(V)
*
*/
for (T node : graph) {
if (dfs(graph, node, visitedNodes, completedNodes)) return true;
}
请您参考如下方法:
简而言之,有向图和无向图的 DFS 复杂度应该是相同的。看来你关于复杂性的论点只适用于特定的图表,我在下面提供了一个更一般的论点供你引用。
符号
给定一个图G = (V, E),我们用n = |V|表示图的顶点数,m = |E| 图的边数。 DFS算法递归给出如下:
Mark all vertices as unexplored
DFS(graph G, start vertex s)
- Mark s as explored
- For every edge (s, v):
- If v is unexplored
- DFS(G, v)
图上 DFS 的复杂度是多少?
它实际上取决于您用于实现图表的底层数据结构。
邻接矩阵是一个 n × n 矩阵,其中 aij (即第 i 行和第 j 行的条目)表示来自顶点 的边的 数量>i 到顶点 j。在这种情况下,DFS 的复杂度为 O(n2)。
邻接表是每个顶点的n个无序列表的集合,每个列表代表其顶点的邻居集合。在这种情况下,DFS 的复杂度为 O(n + m) (对于有向图和无向图)。
证明
首先考虑使用邻接列表来表示图,其中顶点v的列表由指向相邻顶点的指针组成。让mv表示与顶点v相邻的边的数量。由此可见,调用 DFS(G, v)
所需的工作量为 1 + mv(标记 v 进行探索,然后在 mv 边缘上循环)。观察到,从任意顶点 s 开始,DFS 算法在每个顶点上最多递归调用一次(当该顶点未被探索时),因此所需的总工作量为 < em>至多:
Σv ∈ V (1 + mv) = |V| + Σv ∈ V mv
在有向图中,我们有Σv ∈ V mv = |E|,而在无向图中,我们有Σv ∈ V mv = 2 |E|(这是因为(u, v) 和 (v, u) 在无向图中被视为同一条边)。在这两种情况下,所需的总工作量均为 O(|V| + |E|) = O(n + m)。
如果我们使用邻接矩阵来表示图,则 DFS 算法也将为每个顶点最多递归调用一次。但是,如果我们想要在这种情况下循环遍历顶点 v 的所有出边,我们必须循环遍历与 对应的行上的所有条目v 在邻接矩阵中查找所有非零条目,总共需要 n = |V| 次扫描。因此,在这种情况下,DFS 所需的总工作量为 O(|V|2) = O(n2)。