深度优先图算法的时间复杂度 [英] Time complexity of depth-first graph algorithm

问题描述

我开始学习时间复杂度，我在示例中查看了一些简单的时间复杂度。

I am starting to learn time complexity, and I looked in the examples for the time complexity for some simple sort.

我想知道如何计算具有 | V | = n 和 | E | = m ，让开始节点为'u'，结束节点为'v'。

I wanted to know how do we calculate average time complexity for a depth-first search in a graph with |V|=n and |E|=m,let the start node be 'u' and end node be 'v'.

推荐答案

DFS的时间复杂度为O（n + m）。考虑到我们只访问每个节点一次并且在树（没有循环）的情况下，我们越过所有边缘一次的事实，我们得到了这种复杂性。

The time complexity for DFS is O(n + m). We get this complexity considering the fact that we are visiting each node only once and in the case of a tree (no cycles) we are crossing all the edges once.

例如，如果起始节点为u，终止节点为v，我们考虑的是最坏的情况，即v是最后访问的节点。
因此，我们开始访问u所连接组件的第一个邻居，然后访问第二个邻居所连接的组件，依此类推，直到最后一个邻居所连接的组件，在其中找到v。我们仅访问了每个节点一次，并且没有一次跨越同一边缘。

For example, if the start node is u, and the end node is v, we are thinking at the worst-case scenario when v will be the last visited node. So we are starting to visit each the first neighbor's of u connected component, then the second neighbor's connected component, and so on until the last neighbor's connected component, where we find v. We have visited each node only once, and didn't crossed the same edge more than once.

这篇关于深度优先图算法的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！