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