Question
|
Difficulty Level:
2
|
Solution
|
Explanation Quality:4
|
These are the basic questions that you can expect at any software development position
and I am just writing them out here for a quick review but I expect most people
to be already familiar with these questions.
So there are two ways to search a graph, one is depth first search and the other
breadth first search. The name of each algorithm depicts the way the algorithm searches/traverses
the graph datastructure.
For simplicity assume our graph is a tree without cycles. In case of depth search,
we start from the root and go as many levels down the tree as possible, while in
the breadth first search scenario we completly visit all the nodes at one particular
level and then only go to the nodes in the next level.
Here's the code for depth first search, since trees are recursive structures we
write recursive code to implement the algorithm. You can also write an iterative
one which will be slightly more complicated than this one. Also assume we have the
following sample tree on which we are going to run Depth First Search.
Assume that we have to do a depth first search on the tree above and print the value
of each node visited. then the order of visits would be
visit node 4
visit node 2
visit node 1
BACKTRACK to node 2
visit node 3
BACKTRACK to node 2
BACKTRACK to node 4
visit node 6
visit node 5
BACKTACK to node 6
visit node 7
BACKTRACK to node 6
BACKTRACK to node 4
DONE
void DepthFirstSearch(*node){
if(!node->leftChild && !node->rightChild){
//base case
cout<<node->value<<endl; //Print value
of the node
return;
}
if(node->leftChild)
DepthFirstSearch(node->leftChild);
if(node->rightChild)
DepthFirstSearch(node->rightChild);
cout<<node->value<<endl;
}
Note we have assumed and for every other question that appears later on that we
use left edges before we use right edges, that why you see the if condition with
the leftChild coming before the if condition for the rightChild. Moreover, since
we visit every edge and every vertex of the graph/tree the time complexit of O(number
of edges + number of nodes) in the graph.
|