Suppose you have a weighted graph. Starting from a random node, how can you use depth first search (modify the iterative algorithm that uses an explicit stack) to check which nodes exist within a certain weight radius? (Are reachable from this node in a specific weight.)
1 Answers
3
votes
Suppose we use the type Node to denote a node in the graph. In the simplest case, Node could be just an integer (int).
Normally, we use an explicit stack of type Node. In your case, we can use a stack of type pair<Node,int> where pair<A,B> is the type of a pair, and the int represents the distance from your starting point to this Node.
Suppose we are now at Node u with distance d. For an adjacent Node v, let w be the weight of the edge uv. Then just push pair(v, d+w) to the stack. Initially, push pair(v0, 0) where v0 is the starting point of the depth first search.
