• API
• FAQ
• Tools
• Archive
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:}
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)
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)