为什么DFS和BFS的时间复杂度取决于图表的显示方式？ [英] Why does the time complexity of DFS and BFS depend on the way the graph is represented?

问题描述

网站 http：//web.eecs.utk .edu /〜huangj / CS302S04 / notes / graph-searching.html 描述了当使用邻接列表时，DFS和BFS具有复杂度O（V + E），并且如果使用邻接矩阵，复杂度为O（V ² ）。为什么是这样？

The site http://web.eecs.utk.edu/~huangj/CS302S04/notes/graph-searching.html describes that when an adjacency list is used then, DFS and BFS have complexity O(V+E), and if an adjacency matrix is used, the complexity is O(V²). Why is this?

推荐答案

在这两种情况下，运行时间取决于迭代给定给定节点。使用邻接列表，运行时间与输出边的数量成正比。由于每个节点被访问一次，所以成本是节点数加上边的数量，这是O（m + n）。使用邻接矩阵，查找所有出站边缘所需的时间为O（n），因为必须检查节点行中的所有n列。在所有n个节点上进行总结，这样做可以运行到O（n ² ）。

In both cases, the runtime depends on how long it takes to iterate across the outgoing edges of a given node. With an adjacency list, the runtime is directly proportional to the number of outgoing edges. Since each node is visited once, the cost is the number of nodes plus the number of edges, which is O(m + n). With am adjacency matrix, the time required to find all outgoing edges is O(n) because all n columns in the row for a node must be inspected. Summing up across all n nodes, this works out to O(n²).

希望这有帮助！

这篇关于为什么DFS和BFS的时间复杂度取决于图表的显示方式？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！