20.5. Shortest Path in Unweighted Graphs

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. When working with undirected graphs, the problem at hand is to determine if there is a path from a source vertex to a target vertex.

In graphs, we have vertices (points) and edges (connections). An undirected graph means that the connections do not have a direction—if you can go from A to B, you can also go from B to A. The goal is to figure out if you can get from the starting point (source vertex) to another point (target vertex). This is done by checking if there's a path made up of edges connecting these points.

Think of a city map where intersections are the vertices and roads between them are the edges. If you want to find a route from your house (source) to your friend's house (target), you’ll look for streets leading there. Determining if you can reach your friend’s house is akin to finding whether a path exists in the graph.

Graphs can be represented using an adjacency matrix or an adjacency list. The adjacency matrix indicates if there's a direct edge between any two vertices, while the adjacency list saves the neighbors of each vertex to represent the graph more efficiently.

There are two common ways to represent graphs: an adjacency matrix and an adjacency list. An adjacency matrix is a grid that shows whether each pair of vertices is connected by an edge (1 for connected, 0 for not). An adjacency list, on the other hand, lists each vertex followed by its neighbors, making it more space-efficient, especially for graphs with fewer edges relative to vertices.

Imagine a school with classrooms (vertices) and doorways (edges). The adjacency matrix would be like a large table indicating which rooms are directly connected; if you were to write down which rooms connected through doors one by one, that would be like creating an adjacency list.

BFS explores the graph level by level, starting from the source vertex and visiting all directly connected vertices first, followed by those connected to those, and so forth.

BFS is a method for exploring a graph where you start at a source vertex and check all the vertices immediately connected to it. After exploring all of those, you move to the next level of vertices that are connected to your first set. This systematic approach ensures you explore all paths step by step, effectively finding connections in a wide manner.

Imagine you are in a building (the source) and want to tell everyone else (the vertices) something. You first tell the people in your office (direct neighbors) and then, once they all know, they spread the information to their co-workers (next level) until everyone is informed. This way, you’re making sure each level of the building hears the news before moving on.

Every time a vertex is visited in BFS, it is marked to ensure it is not explored again. A queue data structure is used to keep track of vertices to be explored next.

In BFS, it’s crucial to avoid visiting the same vertex multiple times as that could lead to inefficiencies. A 'visited' array marks which vertices have already been explored. A queue is used to manage which vertex you should explore next. As you visit each vertex, you place it in the queue until you systematically explore all connections.

Think of a bread crumbs trail to mark paths taken as you walk through a maze. Each time you reach a new point (vertex), you note it down (mark it as visited) and plan to return to any nearby points you haven't explored yet (manage with a queue). You wouldn’t want to go back to places you’ve already checked where you’ve placed crumbs.

When a vertex is explored, its outgoing edges are looked at to mark new neighbors. If a neighbor hasn’t been visited yet, it gets added to the queue for future exploration.

During exploration, each time you check a vertex, you look at all the edges that go out from it to its neighbors. For each neighbor that hasn't been visited, you mark it as visited and add it to the queue. This ensures that you explore all possible paths stemming from the current vertex, allowing comprehensive coverage of the graph.

Imagine you’re a librarian organizing books. When you read a book (explore a vertex), you check the references (outgoing edges) at the end of that book for more books to read next. If you find a book you've not read yet, you note it down (mark as visited) and add it to your reading list (queue) for later.

The BFS algorithm continues until all reachable vertices have been explored, indicated by an empty queue.

The exploration using BFS concludes when there are no more vertices left in the queue to explore. This signifies that every reachable vertex has been visited, and there are no new discoveries left to make. At this point, the algorithm is complete, and you can summarize the findings.

Returning to the library analogy, after you’ve read all the books on your list (queuing explored vertices), you’ll eventually hit a point where your list is empty. At this point, you can confidently say you’ve explored the entire library for new knowledge.

--