# Depth first search implementation

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);

for (var i = 0; i < adjList.length; 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 + ')');
};

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

doDFS(adjList, 0, false, PVE, PVL, PE);

• 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. – Jonah Nov 21 '15 at 17:23
• Good point. Will do – Daniel Jacobson Nov 21 '15 at 17:32