Posted on Feb 21, 2022

Find Paths in Graphs.

We explored some basics of graphs in this post.
Now let's put some of that knowledge into practice.

Instructions

Find if there is a path between two nodes in a directed graph.

Approach

We iterate through the neighbors of the source node and determine if they are equal to the destination node.
If there is a path from the source's neighbor to the destination then there is a path from the source to the neighbor.

Depth-First Implementation

def hasPath(graph,source,destination): if source==destination: return True for neighbor in graph[source]: if hasPath(graph,neighbor,destination)==True: return True return False graph = { 'a' : ['c','b'], 'b': ['d'], 'c': [ 'e'], 'd': ['f'], 'e': [], 'f': [] } print(hasPath(graph,'e','f'))

Breadth-First Implementation

def hasPath(graph,source,destination): queue = [source] while queue: current = queue.pop(0) if current== destination: return True for neighbor in graph[current]: queue.append(neighbor) return False graph = { 'a': ['c', 'b'], 'b': ['d'], 'c': ['e'], 'd': ['f'], 'e': [], 'f': [] } print(hasPath(graph, 'e', 'f'))

This solution has a time complexity of O(e) where e is the number of edges.
The space complexity is O(n) where n is the number of nodes.

Undirected Graph

We can consider the same problem but for an undirected graph. In an undirected graph we may encounter an endless loop if the nodes are cyclic.

We can handle this by using a set to keep track of visited nodes to avoid visiting them again.

Implementation

def uniPath(edges, source, destination): graph = createGraph(edges) return hasPath(graph, source, destination, set()) def createGraph(edges): graph = {} for edge in edges: x,y = edge if x not in graph: graph[x] = [] if y not in graph: graph[y] = [] graph[x].append(y) graph[y].append(x) return graph def hasPath(graph,source,destination,visited): if source==destination: return True if source in visited: return False visited.add(source) for neighbor in graph[source]: if hasPath(graph,neighbor,destination, visited)==True: return True return False edges = [['i','j'],['k','i'],['m','k'],['k','l'],['o','n']] print(uniPath(edges,'k','n'))