InterviewCrunch

Beta

Find if Path Exists in Graph

Easy

Question

You're given a list of tuples that represent the edges in an undirected graph, and you're given its number of nodes. Return whether there is a valid path in the graph going from one given node to another given node.

Find if Path Exists in Graph Example 1

Input: edges = [(0, 1), (1, 2), (0, 2)], n = 3, source = 0, destination = 2

Output: True

There is at least one valid path going from 0 to 2 (0 -> 1 -> 2 or 0 -> 2).

Find if Path Exists in Graph Example 2

Input: edges = [(0, 1), (0, 2), (3, 4), (3, 5), (4, 5)], n = 6, source = 0, destination = 5

Output: False

There is no path going from node 0 to node 5.

Find if Path Exists in Graph Example 3

Input: edges = [(0, 1), (1, 3), (0, 2), (2, 3), (4, 5)], n = 6, source = 0, destination = 4

Output: False

There is no path going from node 0 to node 4.

Clarify the problem

What are some questions you'd ask an interviewer?

Understand the problem

Which two nodes do NOT have a valid path connecting them in the following graph? edges = [(0, 1), (1, 3), (0, 2), (2, 3), (4, 5)], n = 6
0 to 2
4 to 1
1 to 2
5 to 4

Take a moment to understand the problem and think of your approach before you start coding.

PrevCoding Pattern: Graph Breadth First Search
NextFlood Fill