A Path in a Graph

Internal

• Graphs

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:

https://github.com/ovidiuf/playground/blob/master/algorithms/graphs/adjacency-list/src/main/java/playground/graphs/adj/APath.java