Skip to main content
 首页 » 编程设计

java中验证有向图和无向图的 DFS 复杂性

2025年01月19日7linjiqin

问题:

  1. 有向图和无向图的 DFS 复杂性是否不同?

  2. 如果是,那么有向图复杂度为 O(V + E),无向图复杂度为 O(E) ?其中 E 是边,V 是顶点?

  3. 如果是,则以下注释 - 有向图的 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)