0
$\begingroup$

I am referencing some code I found on GeeksForGeeks.com: Why is the current node printed (and processed) first before its children are processed? Wouldn't "breadth first" mean "Process children first, then process parent"? or, is that only for Trees? I can't be the only one to not understand this, so instead of flaming me, somebody please simply post the answer?

void Graph::DFSUtil(int v, bool visited[]) 
{ 
    visited[v] = true; <-- why is this printed FIRST?
    cout << v << " "; 

    // Recur for all the vertices adjacent 
    // to this vertex 
    list<int>::iterator i; 
    for (i = adj[v].begin(); i != adj[v].end(); ++i) 
        if (!visited[*i]) 
            DFSUtil(*i, visited); 
} 

// DFS traversal of the vertices reachable from v. 
// It uses recursive DFSUtil() 
void Graph::DFS(int v) 
{ 
    // Mark all the vertices as not visited 
    bool *visited = new bool[V]; 
    for (int i = 0; i < V; i++) 
        visited[i] = false; 

    // Call the recursive helper function 
    // to print DFS traversal 
    DFSUtil(v, visited); 
} 
$\endgroup$
  • $\begingroup$ (side note: I'm relatively new here too but as far as I can tell the people are dramatically friendlier than on stackoverflow) $\endgroup$ – Matthew C Dec 2 '19 at 20:22
  • $\begingroup$ this site IS stackoverflow. er, right? $\endgroup$ – eric frazer Dec 2 '19 at 20:33
  • 2
    $\begingroup$ The question is about BFS but the code you posted is for DFS...? $\endgroup$ – Tom van der Zanden Dec 2 '19 at 20:36
  • 1
    $\begingroup$ Welcome to cs.stackexchange! I would recommend against jabs such as "so instead of flaming me, somebody please simply post the answer?" as they discourage users from answering your question, no matter its merits. $\endgroup$ – eru-cs Dec 3 '19 at 1:58
  • $\begingroup$ (Flaming is deprecated, anyway.) $\endgroup$ – greybeard Dec 3 '19 at 8:11
1
$\begingroup$

1) In answer to the semantic question "Wouldn't 'breadth first' mean 'Process children first, then process parent'?"

This question is a duplicate of the following: What is the meaning of 'breadth' in breadth first search?

2) In answer to the technical question "Why is the current node printed (and processed) first before its children are processed?":

BFS processes nodes in the following order: the starting vertex, then all the vertices at distance 1, then all the vertices at distance 2, etc. As pointed out by @user111398, you need to mark a node as visited before processing it or you will go on an infinite loop if the graph is cyclic. If you mark the parent but don't process it before (marking and) processing its children then you are processing the nodes in the following order: all the nodes at max distance, then all the nodes at max depth minus one, etc. This is reverse-BFS, not BFS.

$\endgroup$
0
$\begingroup$

Trees are acyclic. If you have for instance the directed graph $(1,2),(2,1)$ and try running the algorithm with marking visited after the recursive call, you will get a stack overflow. Or for an undirected graph you can consider a triangle $(1,2),(2,3),(1,3)$ which will result in the same thing. For acyclic graphs this issue won't arise so mark visited in either place.

$\endgroup$
  • $\begingroup$ so mark it as "visited" when you first enter function, but don't process it until after the children have been run? $\endgroup$ – eric frazer Dec 2 '19 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.