Find If Path Exists in Graph

Breadth-First SearchGraphUnion Find

Given n nodes labeled from 0 to n - 1 and a list of undirected edges where edges[i] = [a, b] indicates that there is an edge between nodes a and b in the graph, write a function to determine if there exists a path between two nodes start and end in the graph.

Example 1

Input

{
  "n": 3,
  "edges": [
    [
      0,
      1
    ],
    [
      1,
      2
    ],
    [
      2,
      0
    ]
  ],
  "start": 0,
  "end": 2
}

Output

true

Explanation. There is a cycle formed between the nodes, thus there exists a path from node 0 to node 2.

Example 2

Input

{
  "n": 5,
  "edges": [
    [
      0,
      1
    ],
    [
      2,
      3
    ],
    [
      3,
      4
    ]
  ],
  "start": 0,
  "end": 4
}

Output

false

Explanation. Nodes 0 and 4 are not connected directly or indirectly.

Example 3

Input

{
  "n": 4,
  "edges": [
    [
      0,
      1
    ],
    [
      1,
      2
    ]
  ],
  "start": 1,
  "end": 3
}

Output

false

Explanation. There is no path connecting node 1 to node 3.

Follow-up: Can you modify your solution to find the shortest path instead of just any path? How would you handle weighted edges?

Constraints:

1. The number of nodes `n` is in the range `[1, 15]`. 2. The number of edges is in the range `[0, n * (n - 1) / 2]`. 3. All pairs `[a, b]` are unique. 4. `0 <= a, b < n` 5. `a != b` 6. `0 <= start, end < n`

Views: 3