Depth First Search (Adjacency List) in JavaScript

Question

I am trying to implement a DFS search and graphs. How can I make it better?

/**
 * Depth First Search iterative implementation
 * @param: graph to traverse and the starting node
 * @return 
 */
let DfsSearch = function(graph,startNode){
        let stack =  [];
        stack.push(startNode);

        while(stack.length >0){
            let node = stack.pop();
             console.log('visiting node',graph[node].value);
            if(graph[node].isVisited == false){

               graph[node].isVisited = true;
                for(currentNode in graph[node].edges){
                    stack.push(graph[currentNode].value); 
                }
            }

        }

}



module.exports = DfsSearch;


const  DFSSearch= require('./DFS');
/**
 * @description: outputs a new graph , in form of adjancency list 
 * inspired from https://medium.freecodecamp.com/a-gentle-introduction-to-data-structures-how-graphs-work-a223d9ef8837#.4voil9gg6 
 */
let makeGraphs = () => {
    let graph = {};

    //add vertex 
    graph.addVertex = (node) => {
        graph[node] = { edges: {} };
        graph[node].isVisited = false;
        graph[node].value = node; 
    }
    //addedges 
    graph.addEdge = (startNode, endNode) => {
        if (graph.contains(startNode) && graph.contains(endNode)) {

            graph[startNode].edges[endNode] = true;
            graph[endNode].edges[startNode] = true;
        }
    }

    //check if it contains the node
    graph.contains = (node) => {
        if (graph[node]) {
            return true;
        }
        else {
            return false;
        }
    }
    graph.removeEdge = (startNode, endNode) => {
        if (graph.contains(startNode) && graph.contains(endNode)) {
            delete graph[startNode].edges[endNode];
            delete graph[endNode].edges[startNode];
        }
    }
    graph.removeVertex = (node) => {
        if (graph.contains(node)) {
            for (connectedNodes in graph[node].edges) {
                graph.removeEdge(node,connectedNodes);
            }
        }
        delete graph[node];
    }
return graph;
}

let dfsGraph = makeGraphs();
dfsGraph.addVertex(1);
dfsGraph.addVertex(2);
dfsGraph.addVertex(3);
dfsGraph.addVertex(4);
dfsGraph.addVertex(5);
dfsGraph.addEdge(1,2);
dfsGraph.addEdge(1,3);
dfsGraph.addEdge(2,4);
dfsGraph.addEdge(2,5)
DFSSearch(dfsGraph,1);
module.exports= makeGraphs();

Answer 1

Use object literals

Your code currently refers to the graph object about 15 times. This is unnecessary, as the graph object is simply the eventual output of makeGraphs.

So, instead of creating the empty object graph and adding properties and methods later, you can use a single object literal declaration. Using an object literal allows you to abbreviate initialization of object properties and functions.

Where you have:

    let graph = {};

Replace with:

    return {

Then, all subsequent references to graph can then be removed altogether, or, in rare cases where required, replaced with this. Object literals also clean up the look of your other objects, such as edges and nodes.

For example, your addVertex function would look like this:

    addVertex(node) {
        this[node] = {
            edges: {},
            isVisited: false,
            value: node,
        } 
    }

(Note: The arrow operator is not needed because the scope is determined by the object container.)

Handle creating edges / vertices from an array:

The part at the bottom shows how cumbersome it is to add edges and vertices one-by-one. The user would either have to write a loop or a container function. Instead, addEdge and addVertex could be easily modified to take array input. For example:

    addVertex(nodes) {
        for (var node in nodes) {
            this[node]: {
                edges: {},
                isVisited: false,
                value: node,
            }
        } 
    }

Then, to add vertices using addVertex:

dfsGraph.addVertex([1,2,3,4,5])