Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from collections import deque
- def have_route(g, start_node, end_node):
- """Find out if there is a path in a directed graph g
- between start_node and end_node
- Algo #1: BFS-based.
- 0. Check if start_node=end_node. If so, return True;
- 1. Add start_node to queue and while queue is not empty
- 1.1. dequeue curr_node;
- 1.2. for all neigh_node of curr_node, check if neigh=end_node. If found, return True
- immediately. If not, mark it as visited and enqueue;
- 2. We checked the whole connected component of start_node and haven't found end_node
- => return False.
- Complexity
- ----------
- time: O(E+V), space: O(V) - because you need to store visited elements + queue
- Potential algo #2: DFS-based.
- -> always ask what kind of graph we are dealing with!
- Corner cases
- ------------
- 1. Empty graph;
- 2. 1 node;
- 3. start_node==end_node (same as 2?)
- 4. either start_node or end_node is not in the graph
- Parameters
- ----------
- g: dict
- dictionary containing nodes and their neighbours, i.e. {0:[1, 2], 1:[2]}
- start_node: int
- starting node of the route
- end_node: int
- end node of the route
- Returns
- -------
- boolean
- True if there is a route between 2 paths
- """
- q = deque([])
- visited = set()
- if start_node==end_node:
- return True
- q.append(start_node)
- visited.add(start_node)
- while len(q)!=0:
- curr_node = q.popleft()
- for neigh_node in g[curr_node]:
- if neigh_node==end_node:
- return True
- else:
- q.append(neigh_node)
- visited.add(neigh_node)
- return False
- g = {0:[1], 1:[2], 2:[3], 3:[]}
- have_route(g, 2, 0)
- have_route(g, 0, 3)
Add Comment
Please, Sign In to add comment