current position：Home>leetcode 1971. Find if Path Exists in Graph（python）
leetcode 1971. Find if Path Exists in Graph（python）
20220131 09:33:17 【Wang Daya】
「 This is my participation 11 The fourth of the yuegengwen challenge 11 God , Check out the activity details ：2021 One last more challenge 」
describe
There is a bidirectional graph with n vertices, where each vertex is labeled from 0 to n  1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [u_{i}, v_{i}] denotes a bidirectional edge between vertex u_{i} and vertex v_{i}. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.
You want to determine if there is a valid path that exists from vertex start to vertex end.
Given edges and the integers n, start, and end, return true if there is a valid path from start to end, or false otherwise.
Example 1:
Input: n = 3, edges = [[0,1],[1,2],[2,0]], start = 0, end = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
 0 → 1 → 2
 0 → 2
Copy code
Example 2:
Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], start = 0, end = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.
Copy code
Note:
 1 <= n <= 2 * 10^5
 0 <= edges.length <= 2 * 10^5
 edges[i].length == 2
 0 <= u_{i}, v_{i} <= n  1
 u_{i} != v_{i}
 0 <= start, end <= n  1
 There are no duplicate edges.
 There are no self edges.
analysis
According to the meaning , Give an example with n A twoway graph of vertices , Each vertex is marked as 0 To n1 A number in . The edges in the figure are represented as twodimensional integer array edges , Each of them edges[i] = [u_{i}, v_{i}] It means a vertex u_{i} And vertex v_{i} Two way edges between . Each vertex pair is connected by at most one edge , And there are no edges with vertices connected to itself . The question asks to determine whether there is from the vertex start To the top end The effective path . Give edges and integers n、start and end , If there is a valid path from start to end , Then return to true, Otherwise return to false.
Use it directly BFS Ideas ：
 If start be equal to end Go straight back to True （ I didn't expect this border situation , It led to a wrong submission ！！）
 Will all edges There is a twodimensional list of vertices in graph ,graph The length is n
 Initializes a length of n It's all about False Of visited list , Indicates whether a vertex has been accessed , If visited, it becomes True
 Initialize a queue stack , Store that has not been accessed and may be end The summit of , Add a vertex start
 When stack When it's not empty while loop , Take out stack The first element of is key , take visited[key] Set as True Indicates that you have been visited , If end stay graph[key] There has been a direct return in True , Otherwise it would be graph[key] Elements in that have not been accessed are added to stack in , Continue to cycle
 No legal path found at the end of the loop , Go straight back to False
answer
class Solution(object):
def validPath(self, n, edges, start, end):
"""
:type n: int
:type edges: List[List[int]]
:type start: int
:type end: int
:rtype: bool
"""
if start == end: return True
graph = [[] for i in range(n)]
for s,e in edges:
graph[s].append(e)
graph[e].append(s)
visited = [False for _ in range(n)]
stack = [start]
while stack:
key = stack.pop(0)
visited[key] = True
if end in graph[key]:
return True
for vertex in graph[key]:
if not visited[vertex]:
stack.append(vertex)
return False
Copy code
Running results
Runtime: 1612 ms, faster than 97.22% of Python online submissions for Find if Path Exists in Graph.
Memory Usage: 110.9 MB, less than 89.03% of Python online submissions for Find if Path Exists in Graph.
Copy code
Original link ：leetcode.com/problems/fi…
Your support is my greatest motivation
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201310933163862.html
The sidebar is recommended
 Django ORM details  fields, attributes, operations
 Python web crawler  crawling cloud music review (3)
 Stroke list in python (bottom)
 What cat is the most popular? Python crawls the whole network of cat pictures. Which one is your favorite
 [algorithm learning] LCP 06 Take coins (Java / C / C + + / Python / go / trust)
 Python shows the progress of downloading files from requests
 Solve the problem that Django celery beat prompts that the database is incorrectly configured and does not support multiple databases
 Bamboolib: this will be one of the most useful Python libraries you've ever seen
 Python quantitative data warehouse construction 3: data drop library code encapsulation
 The source code and implementation of Django CSRF Middleware
guess what you like

Python hashlib module

The cover of Python 3 web crawler development (Second Edition) has been determined!

The introduction method of executing Python source code or Python source code file (novice, please enter the old bird and turn left)

[Python basics] explain Python basic functions in detail, including teaching and learning

Python web crawler  crawling cloud music review (4)

The first step of scientific research: create Python virtual environment on Linux server

Writing nmap scanning tool in Python  multithreaded version

leetcode 2057. Smallest Index With Equal Value（python）

Bamboolib: this will be one of the most useful Python libraries you've ever seen

Python crawler actual combat, requests module, python realizes capturing a video barrage
Random recommended
 [algorithm learning] 1108 IP address invalidation (Java / C / C + + / Python / go / trust)
 Test platform series (71) Python timed task scheme
 Java AES / ECB / pkcs5padding encryption conversion Python 3
 Loguru: the ultimate Python log solution
 Blurring and anonymizing faces using OpenCV and python
 How fast Python sync and async execute
 Python interface automation test framework (basic)  common data types list & set ()
 Python crawler actual combat, requests module, python realizes capturing video barrage comments of station B
 Python: several implementation methods of multi process
 Sword finger offer II 054 Sum of all values greater than or equal to nodes ｜ 538 ｜ 1038 (Java / C / C + + / Python / go / trust)
 How IOS developers learn python programming 3operator 2
 How IOS developers learn python programming 2operator 1
 [Python applet] 8 lines of code to realize file de duplication
 Python uses the pynvml tool to obtain the working status of GPU
 Data mining: Python actual combat multi factor analysis
 Manually compile opencv on MacOS and Linux and add it to Python / C + + / Java as a dependency
 Use Python VTK to batch read 2D slices and display 3D models
 Complete image cutting using Python version VTK
 Python interface automation test framework (basic)  common data types Dict
 Django (make an epidemic data report)
 Python specific text extraction in actual combat challenges the first step of efficient office
 Daily python, Part 8  if statement
 Django model class 1
 The same Python code draws many different cherry trees. Which one do you like?
 Python code reading (Chapter 54): Fibonacci sequence
 Django model class 2
 Python crawler Basics
 Mapping 3D model surface distances using Python VTK
 How to implement encrypted message signature and verification in Python  HMAC
 leetcode 1945. Sum of Digits of String After Convert（python）
 leetcode 2062. Count Vowel Substrings of a String（python）
 Analysis of Matplotlib module of Python visualization
 Django permission management
 Python integrated programming  visual hot search list and new epidemic situation map
 [Python data collection] scripy realizes picture download
 Python interface automation test framework (basic part)  loop statement of process control for & while
 Daily python, Chapter 9, while loop
 Van * Python  save the crawled data with docx and PDF
 Five life saving Python tips
 Django frequency control