Random walks are ubiquitous in network science, for they are simple yet powerful models of diffusion and information exchange, they also allow to gather information about the network structure finding, e.g., communities, or the deepest node aka the [network median](https://gbertagnolli.github.io/publication/network-depth/). One of the main reasons of their success lies in their mathematics: they are Markov chains on a finite state space with transition probabilities prescribed by the network connectivity. Unfortunately, not all real dynamics satisfy the Markov property and so generalised random walks are needed. In this work, we extensively explore the self-avoiding random walk, and a variation thereof which embeds a resetting mechanism, as an efficient network exploration strategy inspired by the _run-and-tumble_ motion of some bacteria. A significant novelty in this work is provided by the statistical approach we used to describe the evolution of important network features during self-avoiding-type random walks, which are stochastic chains on an evolving state space with structure- and time-dependent transitions.