Find if Path Exists in Graph

Easy

Google

4 views

Topics:

Graphs

You are given a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex source to vertex destination.

Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise.

Here are a couple of examples:

Example 1: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2 Output: true Explanation: There are two paths from vertex 0 to vertex 2:

0 → 1 → 2
0 → 2

Example 2: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5 Output: false Explanation: There is no path from vertex 0 to vertex 5.

Could you implement a function to solve this problem efficiently? What is the time and space complexity of your solution? Also, consider edge cases where the source and destination are the same, or when the graph is disconnected.

Find if Path Exists in Graph

Easy

Google

4 views

Topics:

Graphs

You are given a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex source to vertex destination.

Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise.

Here are a couple of examples:

Example 1: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2 Output: true Explanation: There are two paths from vertex 0 to vertex 2:

0 → 1 → 2
0 → 2

Example 2: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5 Output: false Explanation: There is no path from vertex 0 to vertex 5.

Could you implement a function to solve this problem efficiently? What is the time and space complexity of your solution? Also, consider edge cases where the source and destination are the same, or when the graph is disconnected.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the format of the graph input? Is it represented as an adjacency list, an adjacency matrix, or a list of edges, and what data types are used for the nodes?
Are the graph edges directed or undirected?
What is the expected return value if no path exists between the source and destination nodes? Should I return false, null, or throw an exception?
Can the graph contain cycles or self-loops, and should I handle these cases?
What is the range of possible values for the number of nodes in the graph?

Brute Force Solution

Approach

Imagine a map of cities connected by roads. We want to know if there's any way to get from one specific city to another. The brute force way is to try every single possible route, one after another.

Here's how the algorithm would work step-by-step:

Start at the starting city.
Look at all the cities you can reach directly from the starting city.
For each of those cities, look at all the cities you can reach from *them*.
Keep going, exploring all possible paths, one step at a time.
If you ever reach the destination city, you know a path exists.
If you've tried every possible path and still haven't found the destination, then no path exists.

Code Implementation

def find_if_path_exists_brute_force(number_of_nodes, edges, source_node, destination_node):
    graph = [[] for _ in range(number_of_nodes)]
    for start_node, end_node in edges:
        graph[start_node].append(end_node)
        graph[end_node].append(start_node)

    queue = [source_node]
    visited = [False] * number_of_nodes
    visited[source_node] = True

    while queue:
        current_node = queue.pop(0)

        # If we've found the destination, we're done
        if current_node == destination_node:
            return True

        # Explore all neighbors of the current node

        for neighbor_node in graph[current_node]:
            # Only visit unvisited neighbors to avoid cycles
            if not visited[neighbor_node]:

                visited[neighbor_node] = True
                queue.append(neighbor_node)

    # If we've explored all paths and haven't found the destination, there is no path
    return False

Big(O) Analysis

Time Complexity

O(V + E) – In the worst-case scenario, we might need to visit every vertex (city) and every edge (road) in the graph to determine if a path exists. The number of vertices is represented by V, and the number of edges is represented by E. The algorithm explores all possible paths starting from the source, and each vertex and edge could be visited once. Therefore, the time complexity is proportional to the sum of the number of vertices and edges, resulting in O(V + E).

Space Complexity

O(N) – The space complexity is determined by the size of the data structures used to keep track of visited cities and the cities to explore. In the worst-case scenario, we might add nearly all cities to a queue or stack to be explored, which would be proportional to the number of cities, represented by N. We also need to keep track of the visited nodes using a set or boolean array of size N in the worst case where all nodes are visited. Therefore, the auxiliary space used by the queue or stack and the visited set grows linearly with the number of cities N, resulting in O(N) space complexity.

Optimal Solution

Approach

The problem asks if we can travel between two specific points in a network. We can find this out by systematically exploring the network, marking visited places to avoid repeats. If we reach our destination through this exploration, a path exists.

Here's how the algorithm would work step-by-step:

Start at the beginning point.
Explore all directly connected points from the current point.
If we reach the destination point during exploration, we know a path exists and we are done.
To avoid doing extra work, mark each point we visit so we don't explore it again.
Continue exploring from each new point, always checking if we've reached the destination.
If we run out of new places to explore and haven't found the destination, then there's no path.

Code Implementation

def find_if_path_exists(number_of_nodes, edges, source_node, destination_node):
    graph = [[] for _ in range(number_of_nodes)]
    for start_node, end_node in edges:
        graph[start_node].append(end_node)
        graph[end_node].append(start_node)

    visited_nodes = [False] * number_of_nodes
    queue = [source_node]
    visited_nodes[source_node] = True

    while queue:
        current_node = queue.pop(0)

        # Check if we've found the destination.
        if current_node == destination_node:
            return True

        # Explore all unvisited neighbors.
        for neighbor_node in graph[current_node]:

            # Avoid cycles by checking if the neighbor has been visited
            if not visited_nodes[neighbor_node]:
                visited_nodes[neighbor_node] = True
                queue.append(neighbor_node)

    # No path found after exploring all reachable nodes.
    return False

Big(O) Analysis

Time Complexity

O(n + e) – The time complexity is determined by the graph traversal, where n represents the number of nodes (vertices) and e represents the number of edges in the graph. In the worst-case scenario, we may need to visit each node and traverse each edge once to determine if a path exists. The exploration process ensures that each node and edge are visited at most once (due to the visited marking). Therefore, the time complexity is proportional to the sum of the number of nodes and edges, resulting in O(n + e).

Space Complexity

O(N) – The algorithm uses a data structure to keep track of visited nodes, where N is the number of nodes in the graph. In the worst-case scenario, where all nodes are reachable from the start node, this data structure (e.g., a set or boolean array) will store information about all N nodes. The exploration also uses a queue (or recursion stack in DFS) to hold the nodes to visit next, which in the worst case might contain all N nodes. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Empty graph (no nodes or edges)	If start and end nodes exist and are the same, return true, otherwise return false.
Start and end nodes are the same	Return true immediately as the path exists.
Graph with a single node and no edges	If the start and end are the same single node, return true, otherwise return false.
Disconnected graph where no path can exist between start and end	The search algorithm (BFS/DFS) will terminate without finding the end node, returning false.
Graph with cycles	Use a visited set during traversal to avoid infinite loops caused by cycles.
Large graph exceeding memory limits	Consider an iterative depth-first search or breadth-first search to avoid stack overflow with recursion and/or optimize memory usage of visited set if possible, or explore external memory algorithms if absolutely necessary.
Start or end node does not exist in the graph	Return false, as a path cannot exist if one or both nodes are invalid.
Graph represented with self-loops (edge from a node to itself)	The visited set will prevent infinite loops arising from self-loops.