once this process has completedwe then scan through the memory heap and reclaim any space that is being used for an object that has not been marked at this timewe can also optionally coalesce all the allocated space in the memory heap into single blockthereby eliminating external fragmentation for the time being this scanning and reclamation process is known as the "sweepphaseand when it completeswe resume running the suspended threads thusthe mark-sweep garbage collection algorithm will reclaim unused space in time proportional to the number of live objects and their references plus the size of the memory heap performing dfs in-place the mark-sweep algorithm correctly reclaims unused space in the memory heapbut there is an important issue we must face during the mark phase since we are reclaiming memory space at time when available memory is scarcewe must take care not to use extra space during the garbage collection itself the trouble is that the dfs algorithmin the recursive way we have described it in section can use space proportional to the number of vertices in the graph in the case of garbage collectionthe vertices in our graph are the objects in the memory heaphencewe probably don' have this much memory to use so our only alternative is to find way to perform dfs in-place rather than recursivelythat iswe must perform dfs using only constant amount of additional storage the main idea for performing dfs in-place is to simulate the recursion stack using the edges of the graph (which in the case of garbage collection correspond to object referenceswhen we traverse an edge from visited vertex to new vertex wwe change the edge (vwstored in ' adjacency list to point back to ' parent in the dfs tree when we return back to (simulating the return from the "recursivecall at )we can now switch the edge we modified to point back to of coursewe need to have some way of identifying which edge we need to change back one possibility is to number the references going out of as and so onand storein addition to the mark bit (which we are using for the "visitedtag in our dfs) count identifier that tells us which edges we have modified using count identifier requires an extra word of storage per object this extra word can be avoided in some implementationshowever for examplemany implementations of the java virtual machine represent an object as composition of reference with type identifier (which indicates if this object is an integer or some other typeand as reference to the other objects or data fields for this object since the type reference is always supposed to be the first element of the composition in such implementationswe can use this reference to "markthe edge we changed when leaving an object and going to some object we simply swap the reference at that refers to the type of with the reference at that refers to when we return to vwe can quickly identify the edge (vwwe changedbecause it will be the first reference in the composition for vand the