Skip to main content

Breadth-first search

In breadth-first search (BFS) traversal starts from a single node, and the order of visited nodes is decided based on nodes' distance from the source node. This means that when a certain node is visited, it can be safely assumed that all nodes that are fewer relationships away from the source node have already been visited, resulting in the shortest path from the source node to the newly visited node.

Then you can read the graph, calculate shortest paths with breadth-first search algorithm and draw the results:

import networkx as nx
import matplotlib.pyplot as plt

with open("graph.txt") as f:
lines = f.readlines()

edgeList = [line.strip().split() for line in lines]

g = nx.Graph()

pos = nx.planar_layout(g)

nx.draw(g, pos, with_labels=True, node_color="#f86e00")

bfs = nx.bfs_tree(g, source="go")

nx.draw(bfs, pos, with_labels=True, node_color="#f86e00", edge_color="#dd2222")

Where to next?

There are many graph algorithms libraries out there, with their own implementations of breadth-first search algorithm. NetworkX's algorithms are written in Python, and there are many other libraries that offer faster C++ implementations, such as MAGE, a graph algorithms library developed by Memgraph team.