### View *Find if Path Exists in Graph* on LeetCode

## Statistics

**Time Spent Coding**

7 minutes

**Time Complexity**

O(n) - If the graph is fully connected all the nodes will be visited twice, but mutliples of the growth factor do not increase time complexity, resulting in the O(n) time complexity.

**Space Complexity**

O(n * e) - Every node and all of their edges is stored in the graph, resulting in the O(n * e) space complexity.

**Runtime Beats**

99.49% of other submissions

## Explanation

*The comments explain the majority of the code*

Using `n`

an empty adjacency graph is built, and then using the `edges`

list a that graph is then populated with each nodes connection.

## Algorithm Used

**Breadth-first search -** A tree/matrix traversal algorithm that searches for elements with a given property. Create a queue of elements yet to be visited and then iterate through each level (similar properties) until there are no more elements of the same level.

## Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution:
def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
# Build the bi-directional graph
graph = {}
for i in range(n):
graph[i] = set()
for a,b in edges:
graph[a].add(b)
graph[b].add(a)
# Create varaibles to allow for breadth-first search
visited = set()
q = deque()
q.append(source)
# Continue searching until the queue is empty
while q:
# Iterate through all the nodes on the same level
for _ in range(len(q)):
s = q.popleft()
# If the current node is the destination, return true
if s == destination: return True
# Otherwise, iterate through all the connected nodes and add them to the queue, if unseen
for node in graph[s]:
if node not in visited:
visited.add(node)
q.append(node)
return False