Find if Path Exists in Graph LeetCode solution in Python

1
# Runtime: 1647 ms (Top 68.5%) | Memory: 108.91 MB (Top 50.2%)
2

3

4
class Solution(object):
5
    def validPath(self, n, edges, start, end):
6
        """
7
        :type n: int
8
        :type edges: List[List[int]]
9
        :type start: int
10
        :type end: int
11
        :rtype: bool
12
        """
13
        visited = [False] * n
14
        d = {}
15
        # store the undirected edges for both vertices
16
        for i in edges:
17
            if i[0] in d:
18
                d[i[0]].append(i[1])
19
            else:
20
                d[i[0]] = [i[1]]
21

22
            if i[1] in d:
23
                d[i[1]].append(i[0])
24
            else:
25
                d[i[1]] = [i[0]]
26
        # create a queue as we will apply BFS
27
        q = [start]
28
        while q:
29
            curr = q.pop(0)  # pop the first element as we do in queue
30
            if curr == end:  # if its the end then we can return True
31
                return True
32
            elif (
33
                curr in d and not visited[curr]
34
            ):  # else if it is not the end then check whether its visited or not
35
                q.extend(
36
                    d[curr]
37
                )  # add the adjacent vertices of the current node to the queue
38
            visited[curr] = (
39
                True  # mark this curr vertex as visited = True, so that we dont visit this vertex again
40
            )
41
        return False  # return False if the queue gets empty and we dont reach the end