Public domain image in Wikimedia.

News

Column: Finding a shortest path and Breadth-first search

What is a Breadth-first search? If you have a tree structure as below and visit the root node, and then all of its children, and all of its children’s children, and so on, that’s a so-called Breadth-first search. In this case, the order will be: A => B => C => D => E =>…
<a href="https://highschool.latimes.com/author/johnsong415/" target="_self">John Song</a>

John Song

March 30, 2022

What is a Breadth-first search?

If you have a tree structure as below and visit the root node, and then all of its children, and all of its children’s children, and so on, that’s a so-called Breadth-first search. In this case, the order will be: A => B => C => D => E => F => G => H => I.

(John Song)

(John Song)

This is different from the depth-first search, where you traverse the tree in the “depth-first” way, meaning you go deep down until a leaf, back up and then another leaf, and then move on to the next node and all the way down to one of its leaves, and so on. The order in this case will be: A => B => E => F => C => G => D => H => I – more precisely, this is the pre-order traversal.

(John Song)

(John Song)

Then when would you use BFS?

Finding the shortest path is a good example. There’s a 10 x 8 grid and you want to find the shortest path from (0, 0) to (9, 7). Note there are some obstacles on it, which you should get around.

(John Song)

(John Song)

You’d first want to try the starting point’s neighbors, which are (1, 0) and (0, 1), and then their neighbors again, and so on, until you finally reach the goal. You also want to avoid any obstacles and any “cells” that you already visited. In order to avoid visiting a cell that you already did, you can use a hash set structure (e.g. std::unordered_set in C++), where you store visited cells, and check the cell you’re about to visit against the set before you decide to visit it.

(John Song)

(John Song)

(John Song)

(John Song)

Here’s a quick/simple algorithm for BFS.

(John Song)

(John Song)

Would you like to implement your own?

Column: How I secured an internship at UCLA

Column: How I secured an internship at UCLA

Getting an internship during high school can do wonders for your education, opportunities and not to mention college applications. As a high school junior, some of my friends have been looking for internship opportunities through programs offered at different...

Fountain Valley swim sinks Newport Harbor Sailors

Fountain Valley swim sinks Newport Harbor Sailors

Disclaimer: Reese Meister is a member of the FVHS swim team. Fountain Valley High School’s swim team competed against the Newport Harbor Sailors on April 19. The Barons ultimately pulled through with a narrow win with a final score of 496.5 points to 480.5 points. The...