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.
- Python code
Let's say you have a graph in the
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.