You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: solutions/1001-2000/1971-find-if-path-exists-in-graph.md
+4-5
Original file line number
Diff line number
Diff line change
@@ -1,4 +1,4 @@
1
-
# LeetCode 1971. Find if Path Exists in Graph's Solution
1
+
# LeetCode 1971. Find if Path Exists in Graph's Solution (Breadth-First Search)
2
2
LeetCode problem link: [1971. Find if Path Exists in Graph](https://leetcode.com/problems/find-if-path-exists-in-graph)
3
3
4
4
## LeetCode problem description
@@ -41,7 +41,7 @@ The island problem can be abstracted into a **graph theory** problem. This is an
41
41
42
42

43
43
44
-
And this graph may have multiple **connected components**. At first, we start from `source` vertex which belongs to one of the `connected components`.
44
+
And this graph may have multiple **connected components**. Initially, we start from `source` vertex which belongs to one of the `connected components`.
45
45
46
46

47
47
@@ -53,12 +53,11 @@ We need to find if there is a path from `source` to `destination`. This question
53
53
54
54

55
55
56
-
* As shown in the figure above, **breadth-first search** can be thought of as visiting vertices in rounds and rounds. Actually, whenever you see a question is about
57
-
getting `shortest` or `least` of something of a graph, `breadth-first search` would probably help.
56
+
* As shown in the figure above, **breadth-first search** can be thought of as visiting vertices in rounds and rounds.
58
57
59
58
*`breadth-first search` emphasizes first-in-first-out, so a **queue** is needed.
60
59
61
-
## Approach
60
+
## Approach (Breadth-First Search)
62
61
1. Starting at the `source` vertex, find all the vertices of the `connected component` by `breadth-first search`.
63
62
1. In order to conduct `breadth-first search`, we need to know the adjacent vertices of a vertex. So we need a `map``vertex_to_adjacent_vertices`. We can initialize the `map` by transforming `edges`.
64
63
1. We need to mark all vertices on the same connected component as vertex `source` as `visited` because visited vertices don't need to be visited again.
0 commit comments