A graph representing a search space may include cycles. For example, in the robot delivery domain of Figure 3.7, the robot can go back and forth between nodes $o103$ and $o109$. Some of the aforementioned search methods can get trapped in cycles, continuously repeating the cycle and never finding an answer even in finite graphs. The other methods can loop through cycles, wasting time, but eventually still find a solution.

A simple method of pruning the search, while guaranteeing that a solution will be found in a finite graph, is to ensure that the algorithm does not consider neighbors that are already on the path from the start. Cycle pruning or loop pruning checks whether the last node on the path already appears earlier on the path from the start node to that node. Paths , where $n\in \{n_0,\mathrm{\dots },n_k\}$ are not added to the frontier at line 16 of Figure 3.4 or are discarded when removed from the frontier.

The computational complexity of cycle pruning depends on which search method is used. For depth-first methods, the overhead can be as low as a constant factor, by storing the elements of the current path as a set (e.g., by maintaining a bit that is set when the node is in the path, or using a hash function). For the search strategies that maintain multiple paths – namely, all of those with exponential space in Figure 3.11 – cycle pruning takes time linear in the length of the path being searched. These algorithms cannot do better than searching up the partial path being considered, checking to ensure they do not add a node that already appears in the path.