Graph/bfs library

🎯 Breadth-First Search (BFS)

Traverses an (unweighted) graph level-by-level starting from start. Returns the visitation order as a list of nodes of type T.

  • Input graph is represented as adjacency list: Map<T, List<T>>.
  • If the graph is disconnected, BFS will only visit the component of start.
  • Time complexity: O(V + E)
  • Space complexity: O(V)

Example:

final graph = {
  'A': ['B', 'C'],
  'B': ['D', 'E'],
  'C': ['F'],
  'D': [], 'E': ['F'], 'F': []
};
final order = bfs(graph, 'A');
// order: ['A', 'B', 'C', 'D', 'E', 'F']

Functions

bfs<T>(Map<T, List<T>> graph, T start) → List<T>