Graphs Unveiled: Exploring Shortest Paths with Breadth-First Search

In the world of software engineering, finding the most efficient path between two points is a common challenge, one that can take many forms. Whether it's an AI algorithm strategizing the fewest moves to victory in a game of checkers, a spell-checker computing the minimum number of edits to convert a misspelled word into a correct one, or locating the nearest in-network doctor, the underlying issue is the same. This is where the concept of the shortest path, or the minimum path problem, comes into play.

Let's bring this into a real-world example. Imagine you're in San Francisco, looking to travel from Twin Peaks to the Golden Gate Bridge. You plan to take the bus, aiming to minimize the number of transfers. What algorithm could you use to find the route with the fewest steps?

You'd start by considering whether it's possible to reach your destination in one step. Here are all the locations you can get to in a single step:

The bridge isn't reachable in one step, so what about two steps?

Once again, the bridge eludes us. But what happens at three steps?

Aha! Now the bridge is highlighted in red, indicating that it's possible to reach in three steps.

There may be other routes to the bridge, but they're longer. The algorithm has determined that the shortest path to the bridge requires three steps. This type of problem is solved by an algorithm called Breadth-First Search (BFS), which systematically explores the graph to find the shortest path between two points.

To understand how to go from Twin Peaks to the Golden Gate Bridge using BFS, we need to:

Model the problem using graphs.
Solve the problem using Breadth-First Search.

Let's delve into what graphs are and how BFS can help us find the shortest path.

What is a Graph?

A graph is a set of connections. It's a powerful model used to represent and solve problems involving networks of points, which in graph terminology are called nodes or vertices, connected by lines known as edges.

For example, consider a scenario where you and your friends are playing poker, and you want to keep track of who owes money to whom. You might say, "João owes money to Juan".

A relationship representation between João and Juan in a graph

A graph consists of vertices (like João and Juan) and edges (the relationship that represents who owes money to whom).

That's essentially it—a graph is simply a collection of vertices connected by edges. A vertex can be directly connected to many other vertices, which are referred to as its neighbors. Graphs provide a way to model how different events, people, or points are interconnected.

With this understanding of graphs, we can now explore how to navigate these connections to find the shortest paths using Breadth-First Search.

Breadth-First Search (BFS)

In a previous article, we discussed binary search, an efficient algorithm for finding an item in a sorted array. Breadth-First Search (BFS) is another kind of algorithm entirely, one that leverages graphs to answer questions such as:

Is there a path from vertex A to vertex B?
What is the shortest path from vertex A to vertex B?

BFS operates on the principle of exploring the closest, or neighboring, vertices first before moving on to more distant ones. This approach ensures that if a path exists, it will be found as efficiently as possible. Let's understand BFS with an example involving a practical scenario.

Imagine you own a mango farm and are looking for a mango seller who can market your harvest. You might start by asking, "Do I know any mango sellers on Facebook?" This search process is quite straightforward. First, make a list of friends to search through.

1. Juan
2. Diogo
3. Erick
4. ...

For each friend, you check if they sell mangas:

Does Juan sell mangas? If yes, great! If not, next.
Does Diogo sell mangas? If yes, great! If not, next.
Does Erick sell mangas? If yes, great! If not, next.
...

Suppose none of your immediate friends are mango sellers. You would then need to look at your friends' friends.

As you search each person on your list, if they aren't mango sellers, you add all their friends to your search list. This way, you're not only searching among your friends but also among their friends, and so on. This creates a search pattern that expands outwards, ensuring that you cover your entire network until you find a mango seller. This is Breadth-First Search at work.

Finding the Shortest Path

We've seen how to determine if a path exists between two vertices using BFS. Now, let's figure out how to find the shortest path between them. Can you find the closest mango seller? For instance, your direct friends are first-degree connections, while friends of friends are second-degree connections. Naturally, you'd prefer a first-degree connection over a second-degree one and so on.

It's vital not to search through second-degree connections until you're sure there are no first-degree connections who are mango sellers. The way BFS works, it spreads out from the starting point, ensuring that you check all first-degree connections before moving on to second-degree ones. By following the order of the list—first-degree, then second-degree connections, and so on—you're guaranteed to find the closest mango seller. BFS doesn't just find any path; it finds the shortest path. This is only effective if you maintain the order in which connections are added to the list, adhering to their degree of separation.

In the subsequent section, we'll discuss the role of queues in BFS and how they help maintain the order necessary to ensure the shortest path is found.

Queues

When dealing with the mechanics of the Breadth-First Search algorithm, the data structure that comes into play is the queue. A queue operates much like the queues we're familiar with in everyday life—think of a line of people waiting to buy tickets at a movie theater.

In computer science, a queue is a collection where elements are added to the back and removed from the front, adhering to a First-In-First-Out (FIFO) policy. Imagine a lineup of people: the first person to join the line is the first person to be served and leave the line.

The operations that can be performed on a queue are 'enqueue', which adds an element to the end of the queue, and 'dequeue', which removes an element from the front. If you enqueue two items, the first item will be dequeued before the second—just as in a real-world queue.

enqueue(item1) -> item1 is now at the back of the queue
enqueue(item2) -> item2 is placed behind item1
dequeue() -> item1 is removed from the front of the queue

This behavior is pivotal for the BFS algorithm as it ensures that vertices are explored in the order they were discovered. As you come across new vertices during your search, you enqueue them. When it's time to explore a vertex, you dequeue, ensuring you're always checking the oldest unexplored vertex first, which maintains the breadth-first nature of the search.

Contrast this with a stack, a Last-In-First-Out (LIFO) structure where the last element added is the first to be removed, which is used in another type of graph traversal called Depth-First Search. The choice between using a queue or a stack is what distinguishes BFS from DFS, with each serving different types of problems and goals in graph exploration.

In summary, queues in BFS allow the algorithm to keep track of which vertices to explore next and ensure that the search is conducted level by level, starting from the source vertex and moving outward, thereby guaranteeing the shortest path is found in an unweighted graph.

Implementing a Graph

In the realm of programming, the first step towards solving graph-related problems is to implement a graph in code. A graph comprises nodes, also known as vertices, which are interconnected through edges.

To represent a relationship like "you → Bob", a helpful data structure is a hash table.

Here's a simple representation of a graph in JavaScript:

const graph = {}
graph['you'] = ['alice', 'bob', 'claire']

In this graph, "you" is mapped to an array that contains all your neighbors. But what if we want to extend this graph to include more nodes and connections?

const graph = {}
graph['you'] = ['alice', 'bob', 'claire']
graph['bob'] = ['anuj', 'peggy']
graph['alice'] = ['peggy']
graph['claire'] = ['thom', 'jonny']
graph['anuj'] = []
graph['peggy'] = []
graph['thom'] = []
graph['jonny'] = []

In this expanded graph, Anuj, Peggy, Thom, and Jonny don't have any neighbors. They have edges pointing towards them, but no edges from them to others. This type of graph is called a directed graph (or digraph), where the relationship holds true in only one direction.

Implementing the Algorithm

For a practical application of the Breadth-First Search algorithm, we'll find a mango seller within our network. Here's how we can achieve that:

Create a queue containing all the people to be checked.
Dequeue a person from the queue.
Check if this person is a mango seller.
If yes, you've found the mango seller.
If not, add all their neighbors to the queue.
Repeat steps 2-5.
If the queue is empty, there are no mango sellers in your network.

Here's a JavaScript implementation of the above steps:

Time Complexity

The execution time of Breadth-First Search algorithm mainly involves checking every edge, implying a runtime of at least O(E), where E is the number of edges. In addition, a queue of people is maintained to be checked, with each insertion operation consuming constant time, O(1), leading to an overall time complexity of O(V) for all people, where V is the number of vertices.

Therefore, the total execution time is O(V + E), where V is the number of vertices (or nodes/people), and E is the number of edges (or connections). This efficient time complexity makes Breadth-First Search a useful choice for finding the shortest path in unweighted graphs.

Conclusion

Implementing and understanding graphs are key aspects of being a proficient software engineer. They are not only fundamental data structures, but their wide range of applications from social networks to geographical maps highlight their importance. The Breadth-First Search (BFS) that we covered in this article offers an efficient way to traverse or search a graph, commonly used for finding the shortest path in unweighted graphs. Remember its time complexity is O(V+E), making it efficient for large scale applications.

Though we used JavaScript in this example, knowledge of how to implement a graph and BFS algorithm transcends specific programming languages and is applicable across the board.

Keep honing your algorithms and data structures skills, as they significantly enhance your problem-solving capabilities as a software engineer.

For more articles on latest technologies and guides on mastering foundational concepts, subscribe to the newsletter below.

Keep coding, and see you on the next one! import from "react"