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.
Top comments (0)