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

}

Last modified 4yr ago