“This is the 11th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

describe

There is a bi-directional 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] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. 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 There are two paths from vertex 0 to vertex 2: -1 → 2-0 → 2Copy the code

Example 2:

Input: n = 6, edges = [[0, 1], [0, 2], [3, 5], [5, 4], [4]], start = 0, end = 5 Output: false Explanation: There is no path from vertex 0 to vertex 5.Copy the code

Note:

  • 1 <= n <= 2 * 10^5
  • 0 <= edges.length <= 2 * 10^5
  • edges[i].length == 2
  • 0 <= ui, vi <= n – 1
  • ui! = vi
  • 0 <= start, end <= n – 1
  • There are no duplicate edges.
  • There are no self edges.

parsing

A bidirectional graph with n vertices is given, where each vertex is labeled with a number from 0 to n-1. Edges in the figure are represented as edges of a two-dimensional integer array, where each edge [I] = [UI, vi] represents a bidirectional edge between vertex UI and vertex vi. Each vertex pair is connected by at most one edge, and there is no edge that the vertex is connected to itself. They want to determine whether there is a valid path from vertex start to vertex end. Given edges and integers n, start, and end, return true if there is a valid path from start to end, false otherwise.

Using the BFS idea directly:

  • Return True if start equals end.
  • Let all the vertex cases in the edges have a two-dimensional list graph of length n
  • Initialize an all False visited list of length N, indicating whether a vertex has been visited or True if it has been visited
  • Initialize a queue stack to store unvisited vertices that may be end and add a vertex start
  • When the stack is not empty, the while loop takes out the first element of the stack as key, sets visited[key] to True to indicate that it has been visited, and returns True directly if end appears in graph[key]. Otherwise, add unvisited elements from graph[key] to the stack and continue the loop
  • If no valid path is found at the end of the loop, return 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 the code

The results

The given Path in the linked list is linked to the node in the linked list. Memory Usage: Submissions in Python online submissions for Find if Path Exists in Graph.Copy the code

Original link: leetcode.com/problems/fi…

Your support is my biggest motivation