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: [8],
    2: [],
    1: [],
    8: []
}

There are two ways to traverse this graph
-> Breadth First Search (BFS)
-> 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:
        queue.add(node)
        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: , ,

Leave a Reply

Your email address will not be published. Required fields are marked *