Perhaps cheaper in space, but you will have to do an initial pass over the entire structure to zero your visited bits first, so it may not be cheaper in time.
The GC already needs to sweep through the whole allocated memory to find the unreacheble objects to be freed. Flipping a bit while doing this isnt a big deal.
Since the first pass quit when it finds the first marked node, the zeroing can traverse the structure, erasing marked bits, and stopping at the first 0. The entire structure doesn't have to be visited.