14. (12 marks) Let G (V, E) be an undirected graph in which every vertex is labe

Question

14. (12 marks) Let G (V, E) be an undirected graph in which every vertex is label either "free" or "toll". Write an algorithm that given two "free vertices s and t it decides whether there is at least one path p from s to t that goes only through "free" vertices. If such a path exists the algorithm must return the value true, otherwise it must return the value false. For example, for the following graph (the "free vertices are shaded: 0, 1, 3, 5, 6) if s 0 and t 6 the algorithm must return the value true (as paths (0,1,6) and (0,3, 1,6) are as required); for s 1,t 6, the algorithm must also return true (as path (1,6) only goes through "free vertices); however, for s 0, t 5, the algorithm must return false (as the only paths from vertex 0 to 5 must go through toll" vertices)

Explanation / Answer

We will solve this problem using Stacks....Let us explain how we will handle this
...inputs given: S and T

we will start with vertex S and then push the neighbour vertices which are free...
then pop the vertex from stack then go on....Technique is similar to DFA..
If toll vertex is camme and stack is empty then returns false...or if vertex found
return true..

Algorithm:
----------------

procedure DFS-iterative(G,S,T):
let Stack be a stack
found = false //boolean value to return
Stack.push(S) //pushing inital vertex
while S is not empty
{
v = Stack.pop() //Popping each vertex from stack
if v is T:
found = true; //vertex found..modifty variable
break;
else if v is not labeled as free: { //checking vertex is labeled free..if not leave it
for all edges from v to w in G.adjacentEdges(v) do
Stack.push(w) //pushing neighbours to stack
}   
}
return found;
end procedure

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.