DFS中如何计算时间复杂度？

Question

我想知道DFS算法使用邻接表作为存储结构时的时间复杂度是如何计算的。此外，我想了解计算时间复杂度的一般方法。是计算某个特定关键步骤执行了多少次吗？在这种情况下哪一步应该被视为关键步骤？您能提供计算DFS算法时间复杂度的具体步骤吗？

我试图找到一个特定的语句来计算时间复杂度。但我找不到正确且具体的计算方法。

//here is the data struct
typedef struct ArcNode
{
    int adjvex;
    ArcNode* nextarc;
    ArcType info;
}ArcNode;

typedef struct VNode
{
    VexType data;
    ArcNode* firstarc;
}VNode, AdjList[MVNum];

typedef struct Graph
{
    AdjList vertices;
    int vexnum, arcnum;
}ALGraph;
bool visited[MVNum];
enum Status
{
    OK,
    ERROR
};
Status(*visitFunc)(int);
Status printout(int v)
{
    cout << G.vertices[v].data << endl;
    return OK;
}

//above are some variable definitions, and below are the key DFS algorithms.

void DFS(ALGraph G, int v)
{
    visitFunc(v);
    visited[v] = true;
    ArcNode* w = G.vertices[v].firstarc;
    //this for loop is for traverse the adjacent points.
    for (; w != NULL; w = w->nextarc)
    {
        if (!visited[v])//Should I look at how many times I compare here to calculate the time complexity?
            DFS(G, w->adjvex);//or look at this statement?
    }
}
void DFSTraverse(ALGraph G, Status(*visit)(int v))
{
    int v;
    visitFunc = visit;
    for (v = 0; v < G.vexnum; v++)
    {
        visited[v] = false;
    }
    for (v = 0; v < G.vexnum; v++)
    {
        if (!visited[v])
            DFS(G, v);
    }
}

为什么时间复杂度是

O(N+E)

？

N

是 vex 的数量，

E

是 arc 的数量。我的问题是我应该看看比较“if (!visited[v])”多少次来计算时间复杂度。

Answer 1

使用DFS遍历的示例

假设我们有以下有向图。

我们将在示例中使用的带有循环的 4 节点图。

1. DFS 算法从根顶点 A 开始。它访问它并将其添加到访问集中。
2. 算法沿着从A->B的边访问顶点B并将其添加到访问集中。
3. B 有两个邻居：C 和 D。它任意拾取从 B->C 的边并访问顶点 C。它将顶点 C 添加到访问集中。
4. 它遵循从C->A的边缘。到达 A 后，它意识到自己已经访问过它，因此它回溯到 C 来访问它的下一个邻居。
5. 然后它沿着 C->D 的边，并将 D 添加到访问集，因为它之前没有访问过它。
6. 然后回溯到C，然后到B。它遵循从 B->D 的剩余边缘。然而，当到达D时，它意识到它已经访问过它了。
7. 回溯继续，算法结束，因为它已经访问了所有顶点。

DFS的时间复杂度

DFS算法的时间复杂度取决于具体实现及其所遍历的图或树的特征。

令 V 为图中顶点（或节点）的数量，E 为边的数量。

不同的图形表示

在表示为“邻接矩阵”的图的情况下，由于需要检查每个顶点的所有可能的边，时间复杂度可能为 O(V^2)。另一方面，如果图表示为邻接表，时间复杂度通常为 O(V + E)。 记住，

访问节点

就是“执行特定关键步骤”。 最佳案例

在最好的情况下，DFS 的时间复杂度为

O(V)

。如果图是一棵树（即没有环，并且每个节点只有一个父节点（根除外）），则算法只需要访问图的顶点，而不是边。在这种情况下，所花费的时间与图中的顶点数量成正比。

        A
       / \
      B   C
     /   / \
    D   E   F

最坏情况在最坏的情况下，DFS 的时间复杂度为

O(V + E)

。这是因为 DFS 算法需要多次访问某些节点和边，以便它可以探索整个图。

我们上面探索的 DFS 算法访问了每个节点和每条边。它总共访问了 4

个顶点和

5 个边。因此，算法的时间复杂度为： O(V + E) = O(4 + 5) = O(9)

其中 V 是图中顶点（或节点）的数量，E 是边的数量一般来说，DFS 的时间复杂度是

O(V + E)

，但如果图是树的话，它可以和

O(V) 一样好。 最坏情况的空间

复杂度为 O(V)，因为它需要存储访问过的顶点集或顶点堆栈。