Use Breath-First search to determine if two nodes are connected in a graph.

isConnected.js

/*
 * isConnected.js
 * Determine if a node is connected to another node within a graph.
 * The implementation uses the Breath-first search algorithm.
 * http://en.wikipedia.org/wiki/Breath-first_search
 *
 * Download this file to run the program and its test cases:
 *   % node isConnected.js
 *
 * Sample output:
 *   Showing intra-family members are connected:
 *     'John Doe' and 'John Doe' are connected
 *     'Paul Doe' and 'Mary Doe' are connected
 *     'Susie Jane' and 'Louis Jane' are connected
 *   Showing inter-family members are ✗ NOT ✗ connected:
 *     'Susie Jane' and 'John Doe' are ✗ NOT ✗ connected
 *   Now cross-family connection established...
 *     'Susie Jane' and 'John Doe' are connected
 */

/**
 * Determine if two nodes are connected.
 * @param {Array} connection - A hash of node ID to an array of ID's this node connected to.
 * @param {String|int} startPerson - The starting node ID
 * @param {String|int} targetPerson - The target node ID
 * @returns {boolean} true if starting node and target node are connected, else false.
 */
function isConnected (connection, startPerson, targetPerson) {
    var i, friendPerson, 
        toCheckSet = [],
        checkedSet = [],
        currentPerson;

    toCheckSet.push(startPerson);  //initialize the starting search

    //while still has person to check
    while (toCheckSet.length > 0) {
        currentPerson = toCheckSet.shift();
        checkedSet.push(currentPerson);  //mark the current person as checked
        if (!connection[currentPerson]) {
            //Safety guard - Ignore any person not in the connection
            continue;
        }
        //examin each connection of the current person
        for (i=0; i<connection[currentPerson].length; i++) {
            friendPerson = connection[currentPerson][i];
            if (friendPerson === targetPerson) {
                return true; //we have a connection!
            }
            //enlist this friend for future checking, if not already been checked
            if (checkedSet.indexOf(friendPerson) === -1) {
                toCheckSet.push(friendPerson);
            }
        }
    }
    return false;
} //isConnected


//------------- Test Cases -------------
function tellConnection (network, node1, node2) {
    var status = isConnected(network, node1, node2) ? "connected" : " ✗ NOT ✗ connected";
    console.log("  '%s' and '%s' are %s", node1, node2, status);
}

console.log("----- Test case 1 ------");
var facebook = [];
// Doe family members are connected
facebook["John Doe"] = ["Mary Doe", "Paul Doe"];  
facebook["Mary Doe"] = ["John Doe"];
facebook["Paul Doe"] = ["John Doe"];
// Jane family members are connected
facebook["Susie Jane"] = ["Louis Jane"];
facebook["Louis Jane"] = ["Susie Jane"];

console.log("Showing intra-family members are connected:");
tellConnection(facebook, "John Doe", "John Doe");  //true
tellConnection(facebook, "Paul Doe", "Mary Doe");  //true
tellConnection(facebook, "Susie Jane", "Louis Jane"); //true

console.log("Showing inter-family members are not connected:");
tellConnection(facebook, "Susie Jane", "John Doe");  //false

console.log("Now cross-family connection established...");
facebook["Paul Doe"].push("Louis Jane");
facebook["Louis Jane"].push("Paul Doe");
tellConnection(facebook, "Susie Jane", "John Doe");  //true

console.log("\n----- Test case 2 ------");
var connection = [];
connection[1] = [2, 3, 4];
connection[2] = [1, 3, 4];
connection[3] = [1];
connection[4] = [1];
connection[5] = [6];
connection[6] = [5];

tellConnection(connection, 1, 1); //true
tellConnection(connection, 2, 4); //true
tellConnection(connection, 3, 4); //true
tellConnection(connection, 2, 5); //false
tellConnection(connection, 1, 6); //false