A Path in a Graph: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
(Created page with "=Internal= * Graphs =Overview= Given a directed or undirected graph, find whether there is a path between two nodes.")
 
Line 3: Line 3:
=Overview=
=Overview=
Given a directed or undirected graph, find whether there is a path between two nodes.
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:
<syntaxhighlight lang='java'>
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;
}
</syntaxhighlight>
Playground example: {{External|https://github.com/ovidiuf/playground/blob/master/algorithms/graphs/adjacency-list/src/main/java/playground/graphs/adj/APath.java}}

Revision as of 01:43, 10 November 2021

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:

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