distance between two nodes using breadth first search algorithm using Python

user_13306497 0
Viewed 1912

How can I get just a distance(number of edges) between any two nodes of the graph using BFS algorithms?

I do not want to save the path information as a list (like the code below) to decrease the runtime of the code. (for better performance)

def check_distance(self, satrt, end, max_distance):
    queue = deque([start])
    while queue:
        path = queue.popleft()
        node = path[-1]
        if node == end:
            return len(path)
        elif len(path) > max_distance:
            return False
        else:
            for adjacent in self.graph.get(node, []):
                queue.append(list(path) + [adjacent])
breadth-first-search python
1 Answers

You can increase performance with two changes:

  • As you said, replace paths with distances. This will save memory, more so when the distances are large.
  • Maintain a set of already seen nodes. This will drastically cut the number of possible paths, especially when there are multiple edges per node. If you don't do this, then the algorithm will walk in circles and back-and-forth between nodes.

I would try something like this:

from collections import deque

class Foo:

    def __init__(self, graph):
        self.graph = graph

    def check_distance(self, start, end, max_distance):
        queue = deque([(start, 0)])
        seen = set()
        while queue:
            node, distance = queue.popleft()
            if node in seen or max_distance < distance:
                continue
            seen.add(node)
            if node == end:
                return distance
            for adjacent in self.graph.get(node, []):
                queue.append((adjacent, distance + 1))

graph = {}
graph[1] = [2, 3]
graph[2] = [4]
graph[4] = [5]
foo = Foo(graph)
assert foo.check_distance(1, 2, 10) == 1
assert foo.check_distance(1, 3, 10) == 1
assert foo.check_distance(1, 4, 10) == 2
assert foo.check_distance(1, 5, 10) == 3
assert foo.check_distance(2, 2, 10) == 0
assert foo.check_distance(2, 1, 10) == None
assert foo.check_distance(2, 4, 10) == 1
user_57106370
Related