# Graph Traversal in Python

## Let’s say we have the following graph: graph = { 5: [3, 7], 3: [2, … Read more Graph Traversal in Python

Let’s say we have the following graph:

``````graph = {
5: [3, 7],
3: [2, 1],
7: ,
2: [],
1: [],
8: []
}
``````

There are two ways to traverse this graph
-> Depth First Search (DFS)

BFS can be imagined as horizontal neighbours and DFS can be imagined as vertical neighbours.

Implementation of BFS:

``````def bfs(graph, node, path=[]):
queue = [node]
while queue:
node = queue.pop(0)
if node not in queue:
path.append(node)
for neighbour in graph[node]:
queue.append(neighbour)
return path
``````

Output:

``````>>> bfs(graph, 5)
[5, 3, 7, 2, 1, 8]
``````

Implementation of DFS:

``````def dfs(graph, node, path=[]):
queue = set()
if node not in queue:
path.append(node)
for neighbour in graph[node]:
path = dfs(graph, neighbour)
return path
``````

Output:

``````>>> dfs(graph, 5)
[5, 3, 2, 1, 7, 8]
``````

Source: DEV Community

Categories: NewsTags: , ,