Breadth-First Search (BFS) | Graph Traversal Algorithm

Introduction

Breadth-first search (BFS) is a graph traversal algorithm that visits all the vertices of a graph in breadth-first order, i.e., it visits all the vertices at the same level before moving on to the next level.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL python(("`Python`")) -.-> python/BasicConceptsGroup(["`Basic Concepts`"]) algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) python(("`Python`")) -.-> python/ControlFlowGroup(["`Control Flow`"]) python(("`Python`")) -.-> python/DataStructuresGroup(["`Data Structures`"]) python(("`Python`")) -.-> python/FunctionsGroup(["`Functions`"]) python(("`Python`")) -.-> python/ModulesandPackagesGroup(["`Modules and Packages`"]) python(("`Python`")) -.-> python/ObjectOrientedProgrammingGroup(["`Object-Oriented Programming`"]) python(("`Python`")) -.-> python/ErrorandExceptionHandlingGroup(["`Error and Exception Handling`"]) python/BasicConceptsGroup -.-> python/comments("`Comments`") algorithm/BasicAlgorithmsGroup -.-> algorithm/graphs_trees("`Graphs Trees`") python/BasicConceptsGroup -.-> python/variables_data_types("`Variables and Data Types`") python/BasicConceptsGroup -.-> python/strings("`Strings`") python/BasicConceptsGroup -.-> python/type_conversion("`Type Conversion`") python/ControlFlowGroup -.-> python/conditional_statements("`Conditional Statements`") python/ControlFlowGroup -.-> python/for_loops("`For Loops`") python/ControlFlowGroup -.-> python/while_loops("`While Loops`") python/DataStructuresGroup -.-> python/lists("`Lists`") python/DataStructuresGroup -.-> python/tuples("`Tuples`") python/FunctionsGroup -.-> python/function_definition("`Function Definition`") python/FunctionsGroup -.-> python/default_arguments("`Default Arguments`") python/ModulesandPackagesGroup -.-> python/importing_modules("`Importing Modules`") python/ModulesandPackagesGroup -.-> python/using_packages("`Using Packages`") python/ModulesandPackagesGroup -.-> python/standard_libraries("`Common Standard Libraries`") python/ObjectOrientedProgrammingGroup -.-> python/classes_objects("`Classes and Objects`") python/ObjectOrientedProgrammingGroup -.-> python/constructor("`Constructor`") python/ObjectOrientedProgrammingGroup -.-> python/polymorphism("`Polymorphism`") python/ObjectOrientedProgrammingGroup -.-> python/encapsulation("`Encapsulation`") python/ErrorandExceptionHandlingGroup -.-> python/raising_exceptions("`Raising Exceptions`") python/FunctionsGroup -.-> python/build_in_functions("`Build-in Functions`") subgraph Lab Skills python/comments -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} algorithm/graphs_trees -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} python/variables_data_types -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} python/strings -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} python/type_conversion -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} python/conditional_statements -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} python/for_loops -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} python/while_loops -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} python/lists -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} python/tuples -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} python/function_definition -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} python/default_arguments -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} python/importing_modules -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} python/using_packages -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} python/standard_libraries -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} python/classes_objects -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} python/constructor -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} python/polymorphism -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} python/encapsulation -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} python/raising_exceptions -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} python/build_in_functions -.-> lab-268825{{"`Breadth-First Search Graph Traversal Algorithm`"}} end

Graph Bfs

Problem

Implementing BFS on a graph involves visiting all the vertices of the graph in breadth-first order, starting from a given source vertex. The algorithm works by visiting the source vertex, then visiting all its neighbors, then visiting all the neighbors of its neighbors, and so on. The order in which the vertices are visited is important, as it determines the shortest path from the source vertex to all other vertices in the graph.

Requirements

To implement BFS on a graph, the following requirements must be met:

The graph is directed.
Graph and Node classes are already available.
The graph is connected.
The inputs are valid.
The algorithm fits memory.

Example Usage

Suppose we have a graph with the following edges:

graph.add_edge(0, 1, 5)
graph.add_edge(0, 4, 3)
graph.add_edge(0, 5, 2)
graph.add_edge(1, 3, 5)
graph.add_edge(1, 4, 4)
graph.add_edge(2, 1, 6)
graph.add_edge(3, 2, 7)
graph.add_edge(3, 4, 8)

If we start BFS from vertex 0, the order of nodes visited will be [0, 1, 4, 5, 3, 2]. This means that vertex 0 is visited first, followed by its neighbors 1, 4, and 5, then the neighbors of 1 (3 and 4), then the neighbor of 3 (2).

Summary

In summary, BFS is a graph traversal algorithm that visits all the vertices of a graph in breadth-first order. To implement BFS on a graph, the graph must be directed, connected, and the inputs must be valid. The order in which the vertices are visited is important, as it determines the shortest path from the source vertex to all other vertices in the graph.

Breadth-First Search Graph Traversal Algorithm