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|).
Is that possible to find an algorithm with complexity of O(n) to find an acyclic graph?
Boris Wang
- 63
- 1
- 3