Dive into NumPy! Start organizing, rearranging, and sampling your data.

Python Data Analysis and Visualization

From Python to Numpy

## Breadth-First Algorithm

The breadth-first (as well as depth-first) search algorithm addresses the problem of finding a path between two nodes by examining all possibilities starting from the root node and stopping as soon as a solution has been found (destination node has been reached). This algorithm runs in linear time with complexity in **$O(|V|+|E|)$** (where **$V$** is the number of vertices, and $E$ is the number of edges).



Writing such an algorithm is not especially difficult, provided you have the right data structure. In our case, the array representation of the maze is not the most well-suited and we need to transform it into an actual graph as proposed by [Valentin Bryukhanov](http://bryukh.com/).


$$$$

### Step 1: Implement a Graph Class

# Breadth-First Algorithm

The breadth-first (as well as depth-first) search algorithm addresses the problem of finding a path between two nodes by examining all possibilities starting from the root node and stopping as soon as a solution has been found (destination node has been reached). This algorithm runs in linear time with complexity in **$O(|V|+|E|)$** (where **$V$** is the number of vertices, and $E$ is the number of edges).



Writing such an algorithm is not especially difficult, provided you have the right data structure. In our case, the array representation of the maze is not the most well-suited and we need to transform it into an actual graph as proposed by [Valentin Bryukhanov](http://bryukh.com/).


$$$$

## Step 1: Implement a Graph Class

In this lesson, we will implement the solution of finding shortest path in the maze that we build in the previous lesson. To find the shortest path, we will use the BFS strategy.  

Introduction

Anatomy of an Array

Code Vectorization

Problem Vectorization

Custom Vectorization

Beyond NumPy

Coding Example: Find shortest path in a maze (Breadth-First approach)

Breadth-First Algorithm

Step 1: Implement a Graph Class