## DEV Community 👩‍💻👨‍💻 is a community of 921,001 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

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

``````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
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.

## 🌚 Friends don't let friends browse without dark mode.

Sorry, it's true.