In line 51 , we have declared a map but its empty here whereas on line 44 we are checking the same map . Wouldnt it contain garbage value as it might be possible that all the neighbours of src node are not yet inserted in the map “visited”?
Video Graphs-8 Depth First Search
initially when map “visited” is created by default all values are initialized as “false” because bool type has values false(0) initially.
But the size of map is zero , right ? . How can we even check whether a particular node is visited or not using the map "visited ", when the visited map does not even contain the key- value pair corresponding to that node .
we have atleast one vertex in graph so after this statement
// map<T,bool> visited; declaring the map
// dfshelper(src,visited); calling the function
then with this statement
// visited[node]=true; particular node is marked “true” and a key value pair(node,“true”) is declared
then its corresponding neighbour is marked if they are not marked.
when the dfshelper() is called for the first time ( using src node ) , then its visited is marked true.
After this , we enter the loop because we want check if its neighbours are marked true or not . But at this point , none of the src neighbours have been inserted in the map ( since this is the first call to the dfshelper() ) , so how can we check whether the entry in the visited map for the neighbours is true or false ? I hope you get my point . I had also mentioned the line numbers in my previous comments.
by the concepts it says that we check if(!visited[neighbour]) (this neighbour definately lies in the adjlist[node] and we check whether in the visited map the key “neighbour” exixts with false value or not). and already the nodes are added in the adjlist using add_edge function. and if neighbour is not added we add it with the “true” value(key,value) pair
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.