网上资源说：有向图的生成树可以在 O(|V|+|E|) 时间内找到。请注意，我不是谈论最小生成树。
我正在寻找一种算法，可以在给定有向图 D 的情况下找到任意一棵生成树，其边没有任何关联的权重。
我在网上找不到任何算法。请帮忙。
选择任意顶点作为根，然后继续使用简单的“广度优先搜索”或“深度优先搜索”将相邻顶点添加到树中，直到每个顶点都被访问过一次。使用哈希表（O(1)插入和查找）强制访问每个顶点仅一次以检查以前访问过的顶点。这样你将实现 O(|V| + |E|) 时间复杂度。 其他回答都是错误的。有向图可能有也可能没有生成树。但它将有一个跨越森林。 要找到它，首先执行拓扑排序，假设结果在堆栈中。然后循环直到堆栈为空：从堆栈中弹出一个节点，并构建一个生成树，从弹出的节点运行 DFS，跳过已经访问过的节点。 是的，它是 O(|V|+|E|)。