20.3.2. Data Structures for BFS

A graph consists of a set of vertices and a set of edges, the edges are the connections between the vertices, they may be directed or undirected.

We can represent the structure of the graph through an adjacency matrix. In this adjacency matrix, the i, j'th entry indicates the presence or absence of an edge from vertex i to vertex j. If a[i][j] is 1, there is an edge; if a[i][j] is 0, there is no edge.

Graphs are made up of vertices (nodes) and edges (connections). A simple way to represent this is through an adjacency matrix, which is a square grid that indicates whether pairs of vertices are connected. If one vertex connects to another, the matrix has a 1; if not, it has a 0. This method allows for quick checks of direct connections, but may use a lot of space for sparse graphs since many entries could be zero.

Think of an adjacency matrix like a large seating chart for a party. If two people (vertices) know each other (connected by an edge), you put a checkmark (1) in that seat on the chart. If they don't know each other, it stays empty (0). On a big chart, you might have lots of empty seats if only a few people know each other.

Instead of keeping a row of 1's and 0's, we just record those vertices whose entries are 1. This keeps a more efficient representation for graphs where the number of edges is closer to the number of vertices.

In graphs where there are relatively few connections compared to the number of vertices, using an adjacency list is much more efficient. Instead of a whole grid filled with zeros and ones, you only list the vertices that are connected. This method saves space and makes it easier to look up connections, although checking if a specific pair is connected requires searching through a list instead of just checking a single matrix entry.

Imagine you have a group of friends and instead of writing a complete guest list with everyone connected to everyone (which would be a matrix), you just write down the friends each person relates to. So instead of having 100 names with lots of checkmarks, you might just have a phone book with names and their best friends listed.

Our strategy for finding a path connecting a source vertex to a target vertex follows these steps: We start at the source vertex, mark it as visited, explore all directly connected vertices, and systematically continue exploring while keeping track of which vertices have been visited.

To find a path from a starting point to a target in a graph, we use a methodical approach. We begin at the source vertex, marking it as visited to avoid walking over it again. Then, we explore all neighboring vertices that are directly connected to the source. If any of those neighbors lead to further connections, they are likewise visited and tracked. This ensures we do not miss any potential paths to the goal vertex.

Consider a maze where you start at the entrance (source vertex) and need to find your way out (target vertex). You mark the path you've already traveled to avoid going in circles. As you explore each fork or passage, you tag it on a map, which helps you remember which routes you've already checked, ensuring you explore efficiently until you find the exit.

To keep track of vertices that have been visited but not yet fully explored, we use a queue. Each visited vertex is added to the queue the first time it is encountered, and we explore them in the order they were visited.

In our search strategy, we use a queue to manage which vertices we will explore next. Once we visit a vertex, we add it to the queue. This way, we can systematically explore each vertex in the order they were encountered, ensuring no vertex is overlooked. As we finish exploring each vertex, we check the next one in line in the queue.

Think of this queue as a waiting line at a coffee shop. Each customer (vertex) that orders (is visited) goes to the back of the line to wait for their drink (to be fully explored). The barista (algorithm) serves customers in the order they arrived, ensuring that everyone is eventually attended to without missing anyone.

If at any point the queue is empty, it means all reachable vertices have been visited and explored. At this stage, we can conclude the search.

The process of breadth-first search continues until there are no more vertices left in the queue. When the queue is empty, it signifies that every reachable vertex has been explored from the starting point. This completion is a signal that the search for paths or connections in the graph is finished.

Imagine you are cleaning a room. You have a list (the queue) of places to check (vertices). Once you go through each item on that list and find they are all attended to, your cleaning is complete! The empty list shows that there is nothing left to clean, just like an empty queue shows that there are no more vertices to explore.

The complexity of breadth-first search using an adjacency matrix representation is O(n^2), while using an adjacency list representation drops the complexity to O(n + m), where n is the number of vertices and m is the number of edges.

The efficiency of breadth-first search varies significantly based on how we represent the graph. When we use an adjacency matrix, the algorithm can become slow for large graphs, as it may need to check every possible connection. In contrast, adjacency lists focus directly on existing connections, making the process faster and more resource-efficient.

Think of navigating a city. Using a map that lists every street with detailed connections (adjacency matrix) can be overwhelming and slow to read, especially if many streets aren’t used. Instead, a streamlined map showing only the streets you can actually take (adjacency list) makes it much quicker to find your route, just like how using adjacency lists can speed up a BFS algorithm.

--