DFS on disconnected Graphs

Question

How does DFS(G,v) behaves for disconnected graphs ?

Suppose a graph has 3 connected components and DFS is applied on one of these 3 Connected components, then do we visit every component or just the on whose vertex DFS is applied.

Means Is it correct to say that

DFS on a graph having many components covers only 1 component.

I also tried online DFS visualization tools for disconnected graphs and they also support that it covers only 1 component. But still I want to confirm

• https://www.cs.usfca.edu/~galles/visualization/DFS.html
• https://visualgo.net/dfsbfs

Answer 1

I came up with a way that de DFS could search disconected parts of the graph, i don't know if is the best one but here is below.

    function Node(id, val){
        this.id = id;
        this.val = val;
        this.nodeChildren = {};
    }
    Node.prototype.addAssociation = function(node){
        this.nodeChildren[node.val] = node;
    }

    function Graph(){
        this.nodes = [];
        this.countNodes = 0;
    }
    Graph.prototype.addNode = function(val){
        var n = new Node(this.countNodes, val);
        this.nodes.push(n);
        this.countNodes++;
        return n;
    }

    Graph.prototype.search = function(val){
        var nodeIndex = 0;
        var visited = {}; //Hashmap
        var found = null;

        //Loop within the nodes and check if we didn't found a result yet
        while(nodeIndex < this.nodes.length && found ==null ){

            if(nodeIndex == this.nodes.length) return null;
            var currentNode = this.nodes[nodeIndex];
            nodeIndex++;

            console.log("searching from", currentNode.val, visited);
            found = this.searchDFS(val, visited, currentNode);
        }
        return  found;
    }
    Graph.prototype.searchDFS = function(val, visited, currentNode){

        //Node already visited skip
        if(visited[currentNode.id] ==1 ) {
            console.log("already visited, skipping");
            return null; 
        }

        //Found the node return it
        if(currentNode.val == val){
            return currentNode;
        } 

        visited[currentNode.id] = 1;

        var keys = Object.keys(currentNode.nodeChildren);
        for(var i=0; i<keys.length; i++){
            var childNode = currentNode.nodeChildren[keys[i]];
            if(visited != 1){
                return this.searchDFS(val, visited, childNode);
            }
        }
    }


    var g = new Graph();
    var n1 = g.addNode("a");
    var n2 = g.addNode("b");
    var n3 = g.addNode("c");
    g.addNode("c1").addAssociation(n3);
    g.addNode("c2").addAssociation(n2);
    var n4 = g.addNode("d");
    var n5 = g.addNode("e");
    n1.addAssociation(n2);
    n1.addAssociation(n3);
    n2.addAssociation(n3);
    n3.addAssociation(n4);

    console.log("found", g.search("e"));

Answer 2

Starting a search on a single component of a disconnected graph will search only that component; how could it be otherwise? There's no information to make a decision about when, how or where to move the search to a different component.

If you want to perform a complete search over a disconnected graph, you have two high level options:

• Spin up a separate search of each component, then add some logic to make a choice among multiple results (if necessary). This has the advantage of easy partitioning logic for running searches in parallel.
• Add logic to indicate how to combine the components into a "single" graph. Two ideas for this:
  • Add a dummy root node, and have the components be its children. This would be a neat workaround for tools which only cover one component, but you want to work with all three at once. It also means that if you're searching for a single best result, you're guaranteed to get the global best without any additional checks.
  • Put your components in a list and add logic that jumps to the next one when the search on the current completes. Add additional logic to compare multiple potential search results, if necessary.

Note that the same reasoning applies to breadth first searches as well.