Topological Sort without modifying the graph or marking edges I have a DAG which I want to traverse in a topological order. Wikipedia describes two algorithms for topological sorting, which both work in theory but seem impractical to me from a design point of view: Kahn's algorithm modifies the graph (by removing edges) and the DFS-based one marks nodes, which would require me to modify my node classes (by adding a boolean field) and is furthermore not thread safe.

Are there more practical approaches, that preserve the asymptotic runtime but do not interfere with my business logic so much?
Instead of seting a 'mark' flag;

 node.Marked = true;


You can maintain a set of marked nodes in a hashtable or similar;

 hashTable[node] = true;


You now have to pass the hash table around, but it's O(n) for space and O(1) to check if a node is marked.