0
$\begingroup$

In Breadth-first search and depth-first search, in this source code https://gist.github.com/gennad/791932

public void bfs()
    {
        // BFS uses Queue data structure
        Queue queue = new LinkedList();
        queue.add(this.rootNode);
        printNode(this.rootNode);
        rootNode.visited = true;
        while(!queue.isEmpty()) {
            Node node = (Node)queue.remove();
            Node child=null;
            while((child=getUnvisitedChildNode(node))!=null) {
                child.visited=true;
                printNode(child);
                queue.add(child);
            }
        }
        // Clear visited property of nodes
        clearNodes();
    }

    public void dfs() {
        // DFS uses Stack data structure
        Stack stack = new Stack();
        stack.push(this.rootNode);
        rootNode.visited=true;
        printNode(rootNode);
        while(!stack.isEmpty()) {
            Node node = (Node)s.peek();
            Node child = getUnvisitedChildNode(n);
            if(child != null) {
                child.visited = true;
                printNode(child);
                s.push(child);
            }
            else {
                s.pop();
            }
        }
        // Clear visited property of nodes
        clearNodes();
    }

what is the purpose of visited flag? as I can see it is not used especially if we will use Queue and\or Stack

$\endgroup$
1
$\begingroup$

Graph is a structure where the nodes can be connected arbitrarily and unlike a tree, you can have edges between any two nodes in a graph in any manner or you might also have a node which is not connected at all to any of the other node. For eg. let us say we have a graph and its adjacency list representation as follows:

Graph and its adjacency list

Let us say that we are doing DFS starting with node 1. First neighbor is 3 and in DFS we will visit 3 rightaway we encounter it. Let us suppose we haven't marked 1 as visited. Now we will explore 3. First neighbor is 1 and since it is not marked as visited, the algorithm has no means to know that we have visited this node before. So, we will visit 1 again. From 1, we will visit 3 again and this will be an infinite loop. In order to avoid infinite loops like these we will have to maintain visited flags for the node.

Now you can apply this concept to BFS as well and also to your iterative and recursive implementations of graph traversals.

$\endgroup$
  • $\begingroup$ Is that means in case of trees where each node has only one parent, the flag "visited" is not needed any more ? $\endgroup$ – Melad Basilius Oct 3 '18 at 7:43
  • 1
    $\begingroup$ The thing is that in trees you will never have a cycle. Infact tree is a non cyclic graph. You dont have edges to ancestors, so you can never reach an already visited node and hence there is no need of visited in case of trees. $\endgroup$ – Navjot Waraich Oct 3 '18 at 17:58
2
$\begingroup$

The gist of code in Java you see is NOT complete in the sense that it fails compilation miserably. In that sense, you are looking at an example that is incorrect, not pedagogical and misleading to beginners.

With that having been said, let me explain. The visited flag is used to prevent the function to visit the same node again. It is used in the calls to method getUnvisitedChildNode(Node myNode), whose definition is missing from the gist. Supposedly, that method will return a child node of myNode that is not visited whenever there is at least one such node. Otherwise that method will return null.

I recommend you to read ntroduction to Graph with Breadth First Search(BFS) and Depth First Search(DFS) Traversal Implemented in JAVA, where BFS and DFS are explained clearly. It also has the complete code that contains the partial source code in your question.

$\endgroup$
  • $\begingroup$ I think that code is just pseduo-code. $\endgroup$ – Melad Basilius Oct 2 '18 at 7:11
  • $\begingroup$ Still unclear for me, as i understood after visiting node it will be removed from the Queue or the Stack, so it can not be visited again. $\endgroup$ – Melad Basilius Oct 2 '18 at 7:12
  • $\begingroup$ No, that code is NOT pseudocode. It is Java code proper. In fact, it comes from here, codeproject.com/Articles/32212/…, where you can download the complete code. By the way, I have been writting Java code for over ten years. $\endgroup$ – Apass.Jack Oct 2 '18 at 14:52
  • $\begingroup$ Yes, nodes are removed from the Queue or the Stack once they are visited. However, do you notice how they are added to the Queue or Stack in the first place? It is offered by the call to getUnvisitedChildNode method. How does that method work? It depends on that visited flag! $\endgroup$ – Apass.Jack Oct 2 '18 at 14:54

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.