# Grassfire vs BFS

Expanding on this question :

Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm?

What are the differences between grassfire and BFS? I'm surprised grassfire (supposedly) has a complexity of only $$O(|V|)$$, whereas BFS has a complexity of $$O(|V| + |E|)$$.

• Quoting the answer to the linked question, "In grassfire the distances are constant." – Yuval Filmus Sep 17 at 14:15
• @Yuval Filmus The distances in BFS are constant as well. – J. Schmidt Sep 17 at 14:42
• "Grassfire is actually based on a small modification of BFS." – Yuval Filmus Sep 17 at 14:50
• @Yuval Filmus I can read – J. Schmidt Sep 17 at 14:51
• Grassfire runs in time $O(|V|)$ since a 2D grid has $|E| = \Theta(|V|)$. Grassfire (as described on Wikipedia) has only two passes, whereas BFS can have many iterations. – Yuval Filmus Sep 17 at 14:53

Grassfire seems to be simply a BFS in a 2D grid graph. Since $$|E| = \Theta(|V|)$$ in a 2D grid graph, this results in a complexity of $$O(|V| + |E|) = O(|V|)$$.