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'))

We shall explore more about graphs in other posts.

Blog