Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitfc51fb8

Browse files
committed
1971-find-if-path-exists-in-graph.md Addeddepth-first search in Python.
1 parentdea9b51 commitfc51fb8

File tree

2 files changed

+79
-1
lines changed

2 files changed

+79
-1
lines changed

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

Lines changed: 40 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -40,7 +40,7 @@ Explanation: There is no path from vertex 0 to vertex 5.
4040
Please see[1971. Find if Path Exists in Graph (UnionFind Solution)](1971-find-if-path-exists-in-graph-2.md).
4141

4242
##Intuition
43-
This graph may have multiple**connected components**.
43+
This graph may have multiple**connected components**.
4444

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

@@ -68,6 +68,7 @@ We need to find if there is a path from `source` to `destination`. This question
6868
* Space:`O(n)`.
6969

7070
##Python
71+
###Breadth-first search
7172
```python
7273
classSolution:
7374
defvalidPath(self,n:int,edges: List[List[int]],source:int,destination:int) ->bool:
@@ -93,6 +94,44 @@ class Solution:
9394
returnFalse
9495
```
9596

97+
###Depth-first search
98+
```python
99+
classSolution:
100+
def__init__(self):
101+
self.visited=set()
102+
self.found=False
103+
104+
defvalidPath(self,n:int,edges: List[List[int]],source:int,destination:int) ->bool:
105+
if source== destination:
106+
returnTrue
107+
108+
self.destination= destination
109+
self.vertex_to_vertices= defaultdict(list)
110+
111+
for vertex1, vertex2in edges:
112+
self.vertex_to_vertices[vertex1].append(vertex2)
113+
self.vertex_to_vertices[vertex2].append(vertex1)
114+
115+
self.depth_first_search(source)
116+
117+
returnself.found
118+
119+
defdepth_first_search(self,vertex_):
120+
ifself.found:
121+
return
122+
123+
for vertexinself.vertex_to_vertices[vertex_]:
124+
if vertex==self.destination:
125+
self.found=True
126+
return
127+
128+
if vertexinself.visited:
129+
continue
130+
131+
self.visited.add(vertex)
132+
self.depth_first_search(vertex)
133+
```
134+
96135
##Java
97136
```java
98137
// Welcome to create a PR to complete the code of this language, thanks!

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

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -68,6 +68,7 @@ We need to find if there is a path from `source` to `destination`. This question
6868
* Space:`O(n)`.
6969

7070
##Python
71+
###Breadth-first search
7172
```python
7273
classSolution:
7374
defvalidPath(self,n:int,edges: List[List[int]],source:int,destination:int) ->bool:
@@ -93,6 +94,44 @@ class Solution:
9394
returnFalse
9495
```
9596

97+
###Depth-first search
98+
```python
99+
classSolution:
100+
def__init__(self):
101+
self.visited=set()
102+
self.found=False
103+
104+
defvalidPath(self,n:int,edges: List[List[int]],source:int,destination:int) ->bool:
105+
if source== destination:
106+
returnTrue
107+
108+
self.destination= destination
109+
self.vertex_to_vertices= defaultdict(list)
110+
111+
for vertex1, vertex2in edges:
112+
self.vertex_to_vertices[vertex1].append(vertex2)
113+
self.vertex_to_vertices[vertex2].append(vertex1)
114+
115+
self.depth_first_search(source)
116+
117+
returnself.found
118+
119+
defdepth_first_search(self,vertex_):
120+
ifself.found:
121+
return
122+
123+
for vertexinself.vertex_to_vertices[vertex_]:
124+
if vertex==self.destination:
125+
self.found=True
126+
return
127+
128+
if vertexinself.visited:
129+
continue
130+
131+
self.visited.add(vertex)
132+
self.depth_first_search(vertex)
133+
```
134+
96135
##Java
97136
```java
98137
// Welcome to create a PR to complete the code of this language, thanks!

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp