A Path in a Graph: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
Line 4: Line 4:
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=
=Algorithms=
This is a simpler problem that the [[Shortest_Path_in_a_Graph|shortest path]] or the longest path. Simply modify the [[Graph_Search#DFS_Recursive_Algorithm_Pseudocode|depth-first search]] to exit the recurrence if it sees the target:
This is a simpler problem that the [[Shortest_Path_in_a_Graph|shortest path]] or the [[Longest_Path_in_a_Graph|longest path]]. Simply modify the [[Graph_Search#DFS_Recursive_Algorithm_Pseudocode|depth-first search]] to exit the recurrence if it sees the target:
<syntaxhighlight lang='java'>
<syntaxhighlight lang='java'>
private static boolean foundPathWithDfs(G g, int sid, int tid) {
private static boolean foundPathWithDfs(G g, int sid, int tid) {

Latest revision as of 01:48, 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