基于邻接表的DFS时间复杂度计算方法及相关疑问

时间复杂度计算的通用思路 #

是的，时间复杂度的核心计算方式就是统计算法中关键操作的总执行次数，关键操作指对整体耗时起决定性作用的步骤（比如遍历、核心判断、递归调用等），忽略常数系数和低量级项，只保留最高阶的量级。

DFS中的关键步骤 #

对于邻接表存储的DFS，核心关键步骤包括：

• 每个顶点的访问操作（visitFunc(v)）与标记操作（visited[v] = true）
• 遍历每个顶点邻接边时的指针移动（w = w->nextarc）
• 邻接点的访问状态判断与递归调用

邻接表DFS时间复杂度的具体计算步骤 #

结合你提供的代码，拆解计算如下：

1. 初始化阶段 #

DFSTraverse中第一个循环给visited数组置false，执行次数等于顶点数N，时间复杂度为O(N)。

2. 顶点访问阶段 #

DFSTraverse的第二个循环遍历所有N个顶点，每个顶点只会被访问一次（visited标记后不会再进入DFS）：

• visitFunc(v)和visited[v] = true各执行N次，这部分总耗时O(N)。

3. 边遍历阶段 #

邻接表的结构决定了：

• 无向图中，每条边会在两个顶点的邻接表中各存一个边节点，总边节点数为2E；
• 有向图中，每条边只存一次，总边节点数为E。
  不管哪种情况，DFS中w = w->nextarc的执行总次数等于所有边节点的数量，也就是O(E)量级。

4. 递归与判断操作 #

你代码里的if (!visited[v])存在笔误，正确应该是if (!visited[w->adjvex])——这个判断的执行次数等于边节点总数O(E)，但只有当邻接点未被访问时才会触发递归调用，而递归调用的总次数等于N-1（每个顶点只会被递归访问一次），属于O(N)量级，不会额外增加复杂度。

总复杂度合并 #

把各部分的时间复杂度相加：O(N) + O(N) + O(E) = O(N+E)，这就是最终的时间复杂度。

针对你的疑问解答 #

统计if判断的次数可以作为复杂度分析的一部分，但更核心的是统计所有边节点的遍历次数（指针移动）和顶点访问次数——这两部分共同构成了O(N+E)的来源。你代码中的if判断笔误需要修正，但不影响复杂度分析的逻辑。

附你提供的代码 #

//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);
    }
}

内容的提问来源于stack exchange，提问作者lxzb