---
title: "1971. Find if Path Exists in Graph"
url: "https://laigary.com/interview/coding/1971-find-if-path-exists-in-graph"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2024-02-22"
tags: ["Graph", "Breadth-First Search", "Depth-First Search"]
---

# 1971. Find if Path Exists in Graph

[1971\. Find if Path Exists in Graph](https://leetcode.com/problems/find-if-path-exists-in-graph/)

這個題目有兩個地方要注意，圖形的任兩個節點之間是雙向的，接著就是要選擇要使用深度優先還是廣度優先的搜索。

## 廣度優先

```python
class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        graph = collections.defaultdict(list)
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        # Store all the nodes to be visited in 'queue'.
        visited = set()
        visited.add(source)
        queue = deque([source])
    
        while queue:
            curr = queue.popleft()
            if curr == destination:
                return True

            for child in graph[curr]:
                if child not in visited:                
                    visited.add(child)
                    queue.append(child)
        
        return False
```

## 深度優先

```python
class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        if not edges:
            return source == destination

        table = defaultdict(list)
        for edge in edges:
            table[edge[0]].append(edge[1]) 
            table[edge[1]].append(edge[0])

        visited = set()
        
        def dfs(curr):
            if curr == destination:
                return True
            for node in table[curr]:
                if node not in visited:
                    visited.add(node)
                    if dfs(node):
                        return True
            return False
        
        return dfs(source)
```