Breadth-First Search (BFS) Implementation

J. Carlos Gomez

This project implements a breadth-first search (BFS) algorithm for directed graphs using NetworkX. The Graph class loads a graph from an adjacency list file and provides a bfs method for traversal and shortest-path search.

BFS Method Behavior

The bfs(start, end=None) method supports two modes:

1. Traversal Mode (end is None)
   Returns a list of nodes in the order they are visited using breadth-first traversal starting from the given start node.

2. Pathfinding Mode (end is provided)
   Returns the shortest path from the start node to the end node as a list of nodes.
   If no path exists, the function returns None.

Edge Case Handling

The implementation handles several edge cases:

• Empty graphs return an empty list for traversal and None for pathfinding.
• A missing end node returns None.
• A missing start node raises a ValueError.
• Disconnected graphs return None when no path exists.

Testing

Unit tests are included to verify:

• Correct BFS traversal order
• Correct shortest path computation
• Handling of edge cases such as empty graphs and missing nodes
• Exception handling for invalid inputs