限定最大跳数的BFS中while嵌套for循环的时间复杂度分析

我编写了一个算法，用于返回无向图中与给定节点连通、且在最大跳数范围内的节点列表。

说明：无向图指若节点A与B相连，则B也与A相连。

示例边集如下：

"A", "B"
"A", "C"
"B", "D"
"C", "E"
"E", "F"
"E", "G"

边采用map[string][]string类型的哈希表存储，格式如下：

{"A": ["B","C"]}, {"B": ["A", "D"]}... 以此类推。

调用FindNodes("C", 2)将返回["A", "B", "E", "F", "G"]；调用FindNodes("A", 1)将返回["B", "C"]。

我采用BFS算法实现，逻辑如下：

• 将初始节点加入队列。
• 构建while循环，终止条件为queue为空或counter等于maxHop。
• 获取队列中的节点数量。
• 弹出队首节点，将其标记为currentNode
• 按队列当前节点数构建for循环。
• 嵌套另一层循环遍历currentNode的所有邻居

完整算法实现如下，我对该算法的时间复杂度存在疑惑：我认为它并不具备O(n^3)的时间复杂度，但由于所有for循环和while循环的执行均依赖特定条件，应当如何推导得到正确的时间复杂度？

// FindNodes returns list of nodes connected to a given node and within a max number of hops
// e.g. "A", 2 -> ["B", "C", "D", "E"]
func (ug *UndirectedGraph) FindNodes(node string, maxHops int) []string {
    // if hop number is 0 then it returns the root, node itself.
    if maxHops == 0 {
        return []string{node}
    }

    result := []string{}
    counter := 0
    queue := Queue{Nodes: []string{}}
    queue.add(node)

    for len(queue.Nodes) != 0 && counter != maxHops {

        cnt := len(queue.Nodes)
        for i := 0; i < cnt; i++ {
            currentNode := queue.poll()
            if _, ok := ug.Visited[currentNode]; ok {
                continue
            }

            ug.Visited[currentNode] = true
            neighbours := ug.Edges[currentNode]
            for _, neighbour := range neighbours {
                if _, ok := ug.Visited[neighbour]; !ok {
                    result = append(result, neighbour)
                    queue.add(neighbour)
                }
            }
        }

        counter += 1
    }
    return result
}

这个算法的时间复杂度远低于O(n³)，不要被三层循环的结构误导，直接从BFS的访问逻辑推导即可：

复杂度推导过程 #

1. 首先看节点去重逻辑：你用Visited哈希表标记已访问节点，每个节点最多只会被标记1次，最多也只会被弹出队列处理1次，不存在重复遍历节点的情况。
2. 最外层循环最多执行maxHops次，当maxHops大于连通区域的直径时，队列会提前为空，循环直接终止，不会空跑。
3. 第二层按队列长度遍历的for循环，把所有轮次的执行次数加总，最多等于BFS覆盖到的节点总数——记这个覆盖到的节点数为k，k的上限是图的总节点数n。注意这层循环和最外层不是相乘的关系，是分层计数、总次数累加的关系。
4. 最内层遍历邻居的循环：每个被访问到的节点只会遍历一次自己的邻接表。对于无向图，所有节点邻接表的长度总和等于边数e的2倍（每条边会在两个端点的邻接表里各存一次），所以这层循环的总执行次数上限是2e，和图的总边数线性相关。

最终复杂度结论 #

• 当maxHops足够大，能覆盖起点所在的整个连通区域时，时间复杂度是O(k + e)，如果遍历全图就是标准BFS的O(n + e)，其中n是总节点数，e是总边数。
• 当maxHops较小，还没遍历完连通区域循环就终止时，复杂度和maxHops覆盖范围内的节点数、这些节点关联的边数线性相关，不会出现立方级的复杂度。

额外代码问题提示 #

你现在的Visited是挂载在UndirectedGraph结构体上的字段，多次调用FindNodes时如果不主动重置这个map，会出现访问标记残留导致结果错误，建议把Visited改成函数内部的局部变量，每次调用时单独初始化。

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