memory management and -trees the mark-sweep algorithm in the mark-sweep garbage collection algorithmwe associate "markbit with each object that identifies whether that object is live when we determine at some point that garbage collection is neededwe suspend all other activity and clear the mark bits of all the objects currently allocated in the memory heap we then trace through the active namespaces and we mark all the root objects as "live we must then determine all the other live objects--the ones that are reachable from the root objects to do this efficientlywe can perform depth-first search (see section on the directed graph that is defined by objects reference other objects in this caseeach object in the memory heap is viewed as vertex in directed graphand the reference from one object to another is viewed as directed edge by performing directed dfs from each root objectwe can correctly identify and mark each live object this process is known as the "markphase 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 program 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 do not 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 then switch the edge we modified to point back to wassuming we have some way to identify which edge we need to change back