Поиск в ширину (BFS)

Main Ideas

• In an unweighted graph, every edge has equal length, so a shortest path is the path with the fewest edges.
• Depth-first search (DFS) does not reliably find shortest paths because its traversal order may reach a vertex first by a longer route.
• Breadth-first search (BFS) finds shortest distances by processing vertices in layers:
  1. Start at the source, whose distance is 0.
  2. Process its unvisited neighbors, assigning them distance 1.
  3. Process unvisited neighbors of vertices at distance 1, assigning them distance 2.
  4. Continue until all reachable vertices have been processed.
• A first-in, first-out queue maintains this layer-by-layer order. BFS works on both directed and undirected graphs.

BFS Procedure

1. Initialize every distance to infinity, indicating that it is not yet known.
2. Set the source distance to 0 and add the source to the queue.
3. While the queue is not empty:
   • Remove the earliest-added vertex.
   • Examine each of its neighbors.
   • For each unvisited neighbor:
     • Mark it visited when adding it to the queue.
     • Set its distance to the current vertex’s distance plus 1.
     • Add it to the queue.

Marking a vertex when it is enqueued prevents it from being added multiple times or assigned an incorrect distance. After BFS ends, vertices whose distance is still infinity are unreachable. A program can display a special value for them, such as X, -1, or “impossible.”

Restoring a Shortest Path

• Store a parent (or from) value for each vertex when its distance is first assigned. This records the vertex from which BFS reached it.
• To reconstruct a path to a target, follow parent links from the target back to the source. The source’s parent can be marked with -1.
• Reverse the collected sequence to display the path from source to target.

This parent-array technique is also used in many other shortest-path algorithms.

Complexity and Uses

• Adjacency lists: BFS takes O(V + E) time. Each vertex is queued once, and edges are examined as vertices are processed. In an undirected graph, each edge appears in two adjacency lists.
• Adjacency matrices: Checking for neighbors requires scanning a full row for each vertex, giving O(V²) time.

BFS can be used to:

• Find shortest distances in unweighted graphs.
• Check reachability and find connected components.
• Test whether a graph is bipartite and produce a two-coloring.
• Find the shortest cycle through a specified vertex by running BFS from that vertex and looking for an edge back to it. Finding a shortest cycle anywhere may require running BFS from every vertex.

BFS and DFS

BFS and DFS have similar asymptotic complexity, but their processing orders differ. BFS cannot simply replace DFS for every graph task: it is not suitable for topological sorting or finding strongly connected components, and it does not generally replace DFS for cycle detection.

A non-recursive DFS using a stack is not necessarily equivalent to recursive DFS because the order in which vertices are processed can differ. The simpler version still works for some tasks, such as finding connected components, but other tasks may depend on traversal order. Matching recursive DFS exactly requires a more involved implementation.

Speakers and Sources

• Speaker: One unnamed instructor or narrator.
• Other instructional sources: Graph diagrams, slides, and code examples; no additional speakers are identified.