Graphs Interview Questions Part 2

10. For the following graph:


a depth-first search starting at A, assuming that the left edges in the shown graph are chosen before right edges, and assuming the search remembers previously-visited nodes and will not repeat them, will visit the nodes in the following order:
a. A, B, D, F, E, C, G b. A, B, C, F, E, D, G c. A, B, D, E, F, C, G d. A, B, D, F, E, G, C
Ans:a
11. For the following graph:



Performing the depth first search without remembering previously visited nodes results in visiting nodes in the order
a. B , A, D, F, E, B , A , D, F, E, etc. forever
b. A, D,B, F, E, A, D , B , F, E, etc. forever
c. A, B, D, E, F, A, B, D, E , F etc. forever
d. A, B, D, F, E, A, B, D, F, E, etc. forever
Ans:d
Performing the same search without remembering previously visited nodes results in visiting nodes in the order A, B, D, F, E, A, B, D, F, E, etc. forever, caught in the A, B, D, F, E cycle and never reaching C or G.
12. code(graph G)
{
list L = empty
tree T = empty
choose a starting vertex x
search(x)
while(L is not full)
remove edge (v, w) from end of L
if w not yet visited
{
add (v, w) to T
search(w)
}
}

search(vertex v)
{
visit v
for each edge (v, w)
add edge (v, w) to end of L
}
The code here can represent
a.Depth first search
b.Breadth first seach
c.Prim’s algorithm
d.Kruskal’s algorithm
Ans:a Level:3

13. function (Start, Goal) {
Push(Stack,Start)
while notEmpty(Stack) {
Node := Pop(Stack)
if Node = Goal {
return Node /*the code below does not get executed*/
}
for each Child in Expand(Node) {
if notVisited(Child) {
setVisited(Child)
Push(Stack, Child)
}
}
}
}
The function here can represent
a.Depth first search
b.Breadth first seach
c.Prim’s algorithm
d.Kruskal’s algorithm
Ans:a Level:3

14.The following algorithm represents
1. Put the starting node (the root node) in the queue.
2. Pull a node from the beginning of the queue and examine it.
o If the searched element is found in this node, quit the search and return a result.
o Otherwise push all the (so-far-unexamined) successors of this node into the end of the queue, if there are any.
3. If the queue is empty, every node on the graph has been examined -- quit the search and return "not found".
4. repeat from step 2.
a.Depth first search
b.Breadth first seach
c.Prim’s algorithm
d.Kruskal’s algorithm
Ans:b

15. function (Start, Goal) {
enqueue(Queue,Start)
while notEmpty(Queue) {
Node := dequeue(Queue)
if Node = Goal {
return Node /*the code below does not get executed*/
}
for each Child in Expand(Node) {
if notVisited(Child) {
setVisited(Child)
enqueue(Queue, Child)
}
}
}
}

The function here can represent
a.Depth first search
b.Breadth first seach
c.Prim’s algorithm
d.Kruskal’s algorithm
Ans:b
16. The immense demand for space is the reason why breadth-first search is impractical for larger problems(T/F)
Ans:True
17. Space complexity of breadth-first search where v is the no. of nodes and e is the no. of edges is
a.O(|V| + |E|)
b. O(|E|)
c. O(|V| )
d. O(|V| log |E|)
Ans:a
Since all nodes discovered so far have to be saved, the space complexity of breadth-first search is O(|V| + |E|) where |V| is the number of nodes and |E| the number of edges in the graph