I wonder if I can make an algorithm to check if a given graph $G=(V,E)$ is acyclic or not with the complexity of $O(|V|)$. I modified the BFS algorithm to do this, but the complexity seems to be $O(|V|+|E|)$.
2 of 3
TeX corrections
Is that possible to find an algorithm with complexity of O(n) to find an acyclic graph?
Boris Wang
- 63
- 1
- 3