I have been reading a book on algorithms lately, and I thought I would do a review of the algorithms the book covers. The book, “Grokking Algorithms, Second Edition” by Aditya Bhargava, is well worth a read if you haven’t studied algorithms or if you would like a refresher. In Part 1 of this series, I wrote about the binary search algorithm. In Part 2, I wrote about the selection sort algorithm. In Part 3, I wrote about recursion and one of the algorithms that employs it as a strategy, quicksort.

Today, I start delving into graphs and one of the ways of searching a graph, breadth first search.

Graphs

A graph is a non-linear data structure consisting of nodes (also called vertices) connected by edges. Graphs can represent various types of relationships or networks:

• Vertices (Nodes): Represent entities like cities, people, or data points.
• Edges: Connections between vertices, which can be directed (one-way) or undirected (two-way). Edges might also have weights representing costs, distances, etc.

Graphs come in various forms:

• Directed vs. Undirected: Direction of edges.
• Weighted vs. Unweighted: Presence of edge weights.
• Cyclic vs. Acyclic: Presence of loops in the graph.

Breadth First Search (BFS)

BFS is an algorithm for traversing or searching graph data structures. It explores all neighbors at the present depth level before moving on to nodes at the next depth level. In this example, I use a simple BFS function to traverse a graph of friends looking for a friend who is a mango seller. I am logging multiple steps on the console so you can see what is being checked at each step. The algorithm first searches my friends to check if they are mango sellers. If a person is found not to be a seller, their friends are added to the queue (a FIFO stack) and then they are removed from the stack, and so on through the graph until it finds a mango seller. In the language of graphs, I am checking the vertices and then traversing edges to the next vertex.

An important thing to note - if you are pulling data from a database and then using algorithms like BFS to search the data, how you structure your data matters.Going back to binary search and quicksort, if you put all the people in an array and then loop through your friends to check for mango sellers, you will need to loop through the array of people with every iteration of the friends loop. BFS requires that your people lookups, in this case, be in a hash table so that retrieving a single person is done in O(1) time rather than O(n) time.

Next time, I will dig into trees and Depth First Search.