Coding Towards The Answer, Part 4
Navigating …
3 min readJun 20, 2023
Given a directed graph, design an algorithm to find out whether there is a route between 2 nodes.
Let’s think this through:
We would require a data structure to depict the graph. We use a table, or a dictionary-based representation of a directed graph. Since we have how 1 point is related to many, we can use a node as 1 key, and a value field of an array stating the nodes it is connected to.graph = {
'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D'],
'D': ['E'],
'E': []
}We state the start and end node to trace.start_node = 'A'
end_node = 'E'1. The inputs would be graph, start node, and end node.Caveat: check if the given start node is the end node. If so, it is connected:
if start == end:
return TrueWe will have to trace and end, when we can reach the end node, or when there is no more connected nodes, we can conclude that the 2 ends do not meet. 2. We have to record all that is visited.3. We can use a deque() as a queue data struct to queue up nodes for inspection. Note: deque is a…