75 lines
1.8 KiB
Markdown
75 lines
1.8 KiB
Markdown
# 4.1. Route between nodes
|
|
|
|
> Given a directed graph and two nodes (S and E), is there a route from S to E?
|
|
|
|
A graph can be written like this:
|
|
|
|
```java
|
|
class Graph {
|
|
public Node[] nodes;
|
|
}
|
|
|
|
class Node {
|
|
public String name;
|
|
public Node[] children;
|
|
}
|
|
```
|
|
|
|
The function to find a route from S to E:
|
|
|
|
```java
|
|
bool findRoute(Node S, Node E) {
|
|
Node[] children = S.children;
|
|
for (int i = 0; i < children.size(); i++){
|
|
if (children[i] == E) {
|
|
return True;
|
|
}
|
|
if (children[i].children == Null) {
|
|
continue;
|
|
}
|
|
else if (findRoute(Node children[i].children, E)){
|
|
return True;
|
|
}
|
|
}
|
|
return False;
|
|
}
|
|
```
|
|
|
|
Example, Route from 5 to 11:
|
|
|
|
* 5
|
|
* 2
|
|
* 3
|
|
* 4
|
|
* 1
|
|
* 9
|
|
* 11
|
|
* 6
|
|
|
|
1. children = [2, 1, 6]
|
|
1. Recursive of 2, children = [3, 4]
|
|
2. None of them have children, continue, return False
|
|
2. Back to main loop, continue with children
|
|
1. recursive of 1, children = [9, 11]
|
|
2. found in children[1] == E, return True
|
|
3. Back to main loop, return True
|
|
|
|
Looks good, O(N) where N = all elements in graph, well if the graph isn't balanced at all we might have to iterate through it all.
|
|
|
|
## Hints
|
|
|
|
Two well known algorithms can do this, what are the tradeoffs between them?
|
|
|
|
1. Depth-first search (mine)
|
|
1. Check each node until the end
|
|
2. Breadth-first search
|
|
1. Cheack each main children first, then go deep
|
|
|
|
## Solution
|
|
|
|
Remember to **mark the found nodes as visited to avoid cycles and repetitions of nodes**.
|
|
|
|
For an iterative solution of breadh-first search, see Java files.
|
|
|
|
Depth-first search is a bit simpler to implement since it can be done with simple recursion. Breadth-first search can also be useful to find the shortest path, whereas depth-first search might traverse one adjacent node very deeply before ever going onto the immediate neighbors.
|