gistfile1.js

var MAX_DEPTH = 3;

var work = []; // reusable stack
var seen = []; // "seen hash" 
var run  = 0;

var findPath = function (source, target, u2f, visitor) { // u2f = user to friend
  source = Graph.userToIndex(source);
  target = Graph.userToIndex(target);
  var i = 0;
  var n = 1;
  work[0] = new StackEle(source, 0, -1);
  ++run;
  var max_depth = MAX_DEPTH;
  var steps = 0;
  seen[source] = run;
  while(true) { // iterative BFS
    if(i >= n) {
      return steps;
    }
    var w = work[i];
    var depth = w.depth;
    if(depth > max_depth) {
      break;
    } 
    
    var user = w.user;
    var friends = u2f[user];
    if(!friends) {
      ++i;
      continue;
    }
    var nextDepth = depth+1
    for(var pi = friends.length-1; pi >= 0; --pi) {
      var f = friends[pi];
      ++steps;
      if(f === target) { // we found the goal!
        max_depth = depth;
        var p = [
          work[i],
          new StackEle(f, nextDepth, null)
        ];
        path  = work[i].pos;
        while(path >= 0) { // backtrack on the stack
          p.unshift(work[path])
          path = work[path].pos
        }
        visitor(source, target, p);
      } else {
        if(nextDepth <= max_depth && seen[f] !== run) {
          seen[f] = run; // mark seen hash with current run
          var cur = work[n];
          if(cur) { // reuse stack frames to avoid allocations
            cur.user = f;
            cur.depth = nextDepth;
            cur.pos = i;
          } else {
            work[n] = new StackEle(f, nextDepth, i)
          }
          ++n;
        }
      }
    }
    ++i
  }
  return steps
}

function StackEle(user, depth, position) {
  this.user = user;
  this.depth = depth;
  this.pos   = position
}

findPath;