Route Between Nodes

4.1 Route Between Nodes: Given a directed graph, design an algorithm to find out whether there is a route between two nodes

• Approach 1: Brute force approach:

  • Look a look at each nodes pointers values. If it doesn't exist, then look at those pointers pointers values. Accumulate this process over time. Search the pointers accumulated values over time, searching through this array everytime until your search is exhausted. If one or the other original nodes intersection in there values, then the result is true.

• Approach 2: Breadth first search

  • Iterate through the graph, marking nodes as visited to avoid repetition.

  • Notice how queue's are really nice in exploring and checking all adjacent nodes. Its a nice algorithm to know in general.

// great for lightweight labeling
enum State { Unvisited, Visiting, Visited };

bool isConnected(Graph g, Node *one, Node *two) {
    // same node or no links
    if (one == two || one.getAdjacent() == nullptr || two.getAdjacent() == nullptr)
        return true;

    // mark each node
    for (Node i : g.getNodes()) {
        i.state = State.Unvisited;
    }

    // base case
    one.state = State.Visiting;
    queue<Node*> explore;
    explore.push(one);
    Node *temp = new Node();

    // explore adjacent node starting from arbitrary node
    while (!explore.isEmpty()) {
        // explore one node at a time, and its adjacent pairs
        temp = explore.pop();
        if (temp != nullptr) {
            for (Node i : temp.getAdjacent()) {
                if (i.state == State.Unvisted) {
                    if (i == two) return true;
                    i.state == State.Visiting;
                    explore.push(i);
                }

            }
        }
        temp.state = State.Visited;
    }
    return false;
}