A Path in a Graph
Jump to navigation
Jump to search
Internal
Overview
Given a directed or undirected graph, find whether there is a path between two nodes.
Algorithms
This is a simpler problem that the shortest path or the longest path. Simply modify the depth-first search to exit the recurrence if it sees the target:
private static boolean foundPathWithDfs(G g, int sid, int tid) {
V s = g.vertex(sid);
s.seen = true; // mark v as visited
for(E e: s.edges) { // for every edge (s, w)
V w = e.getVertexOppositeTo(s);
if (w.id == tid) { // if w is the target, we found it, return true
return true;
}
if (!w.seen) { // if w is not visited
if (foundPathWithDfs(g, w.id, tid)) {
return true;
}
}
}
return false;
}
Playground example: