patternMinor
When searching graphs breadth-first and depth-first color the graph. Who un-colors the graph when the search is completed?
Viewed 0 times
depththesearchinggraphsearchwhobreadthgraphscolorcolors
Problem
The depth-first and breadth-first algorithms for traversing graphs use a flag (or color) to mark nodes when they are visited. For example some forms of the algorithms use white/grey/black as colors. When the traversal is complete all the nodes in the graph are black.
None of the material I have been reading on these algorithms mentions anything about reverting all the nodes back to white when the traversal is complete.
Are there some extra steps we can add to the algorithms to take care of this? Or must we traverse the graph all over again to reset each node's color? Or perhaps the Graph's data structure is such that changes to the flag/color is temporary and is lost once the traversal is complete?
None of the material I have been reading on these algorithms mentions anything about reverting all the nodes back to white when the traversal is complete.
Are there some extra steps we can add to the algorithms to take care of this? Or must we traverse the graph all over again to reset each node's color? Or perhaps the Graph's data structure is such that changes to the flag/color is temporary and is lost once the traversal is complete?
Solution
Your question is, essentiall, "How is this stuff implemented?", to which the answer is "However the implemnter chooses."
Although we talk about nodes of the graph being coloured during the search, implementing that literally as a "visited" field in each node's data record would take up storage space even when no search is in progress. In a concurrent environment, it would also limit you to doing only one search at a time. Instead, it's normal to implement the colouring as a list of visited nodes, or some other structure that is external to the representation of the graph itself; this is typically made explicit in descriptions of, e.g., A* search. This data structure will simply be deallocated when the search is complete.
If you did have an explicit "visited" field in each node then, yes, you'd need to do a separate pass to clear those after each search.
Although we talk about nodes of the graph being coloured during the search, implementing that literally as a "visited" field in each node's data record would take up storage space even when no search is in progress. In a concurrent environment, it would also limit you to doing only one search at a time. Instead, it's normal to implement the colouring as a list of visited nodes, or some other structure that is external to the representation of the graph itself; this is typically made explicit in descriptions of, e.g., A* search. This data structure will simply be deallocated when the search is complete.
If you did have an explicit "visited" field in each node then, yes, you'd need to do a separate pass to clear those after each search.
Context
StackExchange Computer Science Q#102520, answer score: 3
Revisions (0)
No revisions yet.