Skip to content

Commit b5979d7

Browse files
committed
Added (Breadth-First Search) to title.
1 parent 2f3fec6 commit b5979d7

File tree

1 file changed

+4
-5
lines changed

1 file changed

+4
-5
lines changed

solutions/1001-2000/1971-find-if-path-exists-in-graph.md

+4-5
Original file line numberDiff line numberDiff 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)
22
LeetCode problem link: [1971. Find if Path Exists in Graph](https://leetcode.com/problems/find-if-path-exists-in-graph)
33

44
## LeetCode problem description
@@ -41,7 +41,7 @@ The island problem can be abstracted into a **graph theory** problem. This is an
4141

4242
![](../../images/graph_undirected_1.svg)
4343

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`.
4545

4646
![](../../images/graph_undirected_2.png)
4747

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

5454
![](../../images/binary_tree_BFS_1.gif)
5555

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.
5857

5958
* `breadth-first search` emphasizes first-in-first-out, so a **queue** is needed.
6059

61-
## Approach
60+
## Approach (Breadth-First Search)
6261
1. Starting at the `source` vertex, find all the vertices of the `connected component` by `breadth-first search`.
6362
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`.
6463
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

Comments
 (0)