Graph: Check if a Path Exists in an Undirected Graph

Problem Description:

You are given an undirected graph represented by a list of edges. Each edge connects two nodes. Your task is to determine if there exists a path between two given nodes, start and end, using Depth-First Search (DFS).

• Input:
  • An array of edges, where each edge is a pair of integers [u, v], representing an undirected edge between node u and node v.
  • An integer start, the starting node.
  • An integer end, the destination node.
  • An integer n, the total number of nodes in the graph (labeled 0 to n-1).
• Output:
  • Return true if there exists a path from start to end, otherwise return false.

Constraints:

• The graph may contain cycles.
• The graph is undirected, meaning if there is an edge from node u to node v, there is also an edge from v to u.
• The graph may not be connected. There may be isolated nodes that do not have any neighbors.

Example 1:

Input:

int[][] edges = {{0, 1}, {1, 2}, {2, 3}, {3, 4}};
int start = 0, end = 4, n = 5;

Output:

true

Explanation: There is a path from node 0 to node 4: 0 → 1 → 2 → 3 → 4.

---

Example 2:

Input:

int[][] edges = {{0, 1}, {1, 2}, {2, 3}, {3, 4}};
int start = 0, end = 5, n = 5;

Output:

false

Explanation: There is no node 5 in the graph, so no path can exist.

---

Example 3:

Input:

int[][] edges = {{0, 1}, {1, 2}, {2, 3}};
int start = 0, end = 3, n = 4;

Output:

true

Explanation: There is a path from node 0 to node 3: 0 → 1 → 2 → 3.

---

Solution Approach

1. Graph Representation:
   • Build an adjacency list from the given edges.
2. DFS Traversal:
   • Perform DFS starting from the start node.
   • If during the traversal, the end node is encountered, return true.
   • Mark each node as visited to prevent revisiting and avoid cycles.
3. Edge Cases:
   • If the start node is the same as the end node, return true immediately.
   • If the graph contains isolated nodes or no edges, make sure to return false if there is no path.

---

Code Example (Java)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class GraphPath {

  public static boolean hasPath(int[][] edges, int start, int end, int n) {
    // Step 1: Build Graph (Adjacency List)
    Map<Integer, List<Integer>> graph = new HashMap<>();
    for (int i = 0; i < n; i++) {
      graph.put(i, new ArrayList<>());
    }
    for (int[] edge : edges) {
      graph.get(edge[0]).add(edge[1]);
      graph.get(edge[1]).add(edge[0]); // Undirected graph
    }

    // Step 2: Use DFS to find path
    Set<Integer> visited = new HashSet<>();
    return dfs(graph, start, end, visited);
  }

  private static boolean dfs(Map<Integer, List<Integer>> graph, int current, int end,
      Set<Integer> visited) {
    if (current == end) {
      return true;
    }
    if (visited.contains(current)) {
      return false;
    }

    visited.add(current);
    for (int neighbor : graph.get(current)) {
      if (dfs(graph, neighbor, end, visited)) {
        return true;
      }
    }
    return false;
  }

  public static void main(String[] args) {
    int[][] edges = {{0, 1}, {1, 2}, {2, 3}, {3, 4}};
    int start = 0, end = 4, n = 5;

    System.out.println(hasPath(edges, start, end, n)); // Output: true
  }
}