SHARE
TWEET

Untitled

a guest Jan 11th, 2019 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from collections import deque
  2.  
  3. def have_route(g, start_node, end_node):
  4.     """Find out if there is a path in a directed graph g
  5.     between start_node and end_node
  6.        
  7.     Algo #1: BFS-based.
  8.         0. Check if start_node=end_node. If so, return True;
  9.         1. Add start_node to queue and while queue is not empty
  10.             1.1. dequeue curr_node;
  11.             1.2. for all neigh_node of curr_node, check if neigh=end_node. If found, return True
  12.             immediately. If not, mark it as visited and enqueue;
  13.         2. We checked the whole connected component of start_node and haven't found end_node
  14.            => return False.
  15.  
  16.     Complexity
  17.     ----------
  18.     time: O(E+V), space: O(V) - because you need to store visited elements + queue
  19.    
  20.     Potential algo #2: DFS-based.
  21.    
  22.    
  23.     -> always ask what kind of graph we are dealing with!
  24.    
  25.     Corner cases
  26.     ------------
  27.     1. Empty graph;
  28.     2. 1 node;
  29.     3. start_node==end_node (same as 2?)
  30.     4. either start_node or end_node is not in the graph
  31.    
  32.    
  33.     Parameters
  34.     ----------
  35.     g: dict
  36.         dictionary containing nodes and their neighbours, i.e. {0:[1, 2], 1:[2]}
  37.     start_node: int
  38.         starting node of the route
  39.     end_node: int
  40.         end node of the route
  41.    
  42.     Returns
  43.     -------
  44.     boolean
  45.         True if there is a route between 2 paths
  46.     """
  47.    
  48.     q = deque([])
  49.     visited = set()
  50.    
  51.     if start_node==end_node:
  52.         return True
  53.     q.append(start_node)
  54.     visited.add(start_node)
  55.    
  56.     while len(q)!=0:
  57.         curr_node = q.popleft()
  58.         for neigh_node in g[curr_node]:
  59.             if neigh_node==end_node:
  60.                 return True
  61.             else:
  62.                 q.append(neigh_node)
  63.                 visited.add(neigh_node)
  64.        
  65.     return False
  66.  
  67. g = {0:[1], 1:[2], 2:[3], 3:[]}
  68. have_route(g, 2, 0)
  69. have_route(g, 0, 3)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top