如何在O(|V|)时间复杂度内判断有向图中顶点是否存在自环？

核心思路 #

自环的定义是顶点u存在一条从自身指向自身的边。基于你提供的std::map<T, std::set<T>>存储结构，直接检查目标顶点的邻接集合中是否包含自身即可——这个操作的时间复杂度实际为O(log|V|)，完全满足你要求的O(|V|)复杂度。

最优实现代码 #

template <class T>
bool Digraph<T>::loop(T u) const {
    // 查找顶点u是否存在于图中
    auto vertex_it = graph.find(u);
    if (vertex_it == graph.end()) {
        // 顶点不存在，无自环
        return false;
    }
    // 检查u的邻接集合中是否包含自身
    return vertex_it->second.count(u) > 0;
}

复杂度说明 #

• std::map的find操作：O(log|V|)
• std::set的count操作：O(log|E_u|)（|E_u|为顶点u的出边数量）
• 整体复杂度远低于O(|V|)，完全符合需求

严格O(|V|)实现（冗余但符合要求） #

如果一定要强制用O(|V|)的遍历方式实现（不推荐，效率更低），可以遍历所有顶点：

template <class T>
bool Digraph<T>::loop(T u) const {
    for (const auto& entry : graph) {
        if (entry.first == u) {
            return entry.second.count(u) > 0;
        }
    }
    return false;
}

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