3
\$\begingroup\$

I've been practicing my algorithms using The Algorithm Design Manual. I've decided to implement the depth first search section (5.8) using javascript. Note you can execute the code here if you don't have node.js.

var doDFS = function(graph, source, directed, processVertexEarly, processVertexLate, processEdge, logOff) {
    var finished = false;
    var time = 0;
    var discovered = [];
    var processed = [];
    var entry_time = [];
    var exit_time = [];
    var parent = [];

    if (!logOff) console.log();
    if (!logOff) console.log('*****************************');
    if (!logOff) console.log('DFS starting at', source, 'for adjacency list:');
    if (!logOff) console.log(graph);

    (function recDoDFS(u) {
        if (finished) return;
        discovered[u] = true;
        if (!logOff) console.log('DISCOVERED', u);
        time = ++time;
        entry_time[u] = time;

        processVertexEarly(u);

        var adjList = graph[u];
        for (var i = 0; i < adjList.length; i++) {
            v = adjList[i];
            if (!discovered[v]) {
                parent[v] = u;
                recDoDFS(v);
            } else if (!processed[v] || directed) {
                processEdge(u, v);

                if (finished) return;
            }
        }
        processVertexLate(u);

        time = ++time;
        exit_time[u] = time;

        processed[u] = true;
    })(source);

    if (!logOff) console.log();
    if (!logOff) console.log('%%%%%%%%%%%%%%% DFS Info %%%%%%%%%%%%%%%');
    for (var i = 0; i < graph.length; i++) {
        if (!logOff) console.log();
        if (!logOff) console.log('NODE', i);
        if (!logOff) console.log('discovered:', discovered[i]);
        if (!logOff) console.log('processed:', processed[i]);
        if (!logOff) console.log('parent:', parent[i]);
        if (!logOff) console.log('entry time:', entry_time[i]);
        if (!logOff) console.log('exit time:', exit_time[i]);
        if (!logOff) console.log();
    }
    if (!logOff) console.log('############ DFS OVER ############');
    if (!logOff) console.log();
};

var PVE = function(v, logOff) {
    if (!logOff) console.log('Early processed vertex:', v);
};

var PVL = function(v, logOff) {
    if (!logOff) console.log('Late processed vertex:', v);
};

var PE = function(u, v, logOff) {
    if (!logOff) console.log('Processed edge:', '(' + u + ', ' + v + ')');
};

var adjList = [
    [1],
    [0, 4, 5],
    [3, 4, 5],
    [2, 6],
    [1, 2],
    [1, 2, 6],
    [3, 5],
    [8],
    [],
    []
];

doDFS(adjList, 0, false, PVE, PVL, PE);
\$\endgroup\$
  • \$\begingroup\$ Hey Daniel, looks like you've posted 8 questions but only selected an answer on one of them. Consider accepting the most helpful answer on your previous posts before posting new questions. \$\endgroup\$ – Jonah Nov 21 '15 at 17:23
  • 1
    \$\begingroup\$ Good point. Will do \$\endgroup\$ – Daniel Jacobson Nov 21 '15 at 17:32

Your Answer

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

Browse other questions tagged or ask your own question.