19.1.4. Finding Paths

So, recall that a graph is a set of vertices or nodes V connected by a set of edges E. We can have two types of edges: undirected edges and directed edges.

A graph consists of points called vertices (or nodes) that are connected by lines called edges. There are two kinds of edges: undirected edges, which simply connect any two vertices without direction, and directed edges, which have a specific direction from one vertex to another.

Imagine a social network as a graph. Each person is a vertex, and a friendship is an undirected edge since both friends can connect with each other. In contrast, if you think about a Twitter follower, where one user can follow another without reciprocation, that represents a directed edge.

We saw two typical problems involving finding a route, which can be represented for both undirected and directed graphs.

There are methods to find paths in both directed and undirected graphs. In directed graphs, finding a path involves tracing connections that follow the direction specified by the edges. In undirected graphs, you simply look for any connection between vertices without worrying about direction.

Consider a map of cities: finding a route from City A to City B may involve one-way streets (directed) or a network of roads where you can travel in both directions (undirected).

When we write an algorithm to manipulate a graph, how do we get the algorithm to look at the picture?

To enable algorithms to work with graphs, we need to represent them in a way that the algorithms can process. This often involves assigning numbers to vertices and maintaining a record of edges in either an adjacency matrix or list to guide the algorithm in determining connectivity.

Think of a graph as a recipe book where each recipe (vertex) tells you what ingredients (edges) are needed. If you want to find the path from one recipe to another, you need a table of contents (the graph representation) that helps you navigate through the recipes.

One thing we can do with the adjacency matrix is find all the neighbors of a vertex.

Using an adjacency matrix, you can easily find all the neighbors of a specific vertex by looking at its corresponding row. Each '1' in that row indicates a direct connection (neighbor) to another vertex.

Imagine a classroom where every student (vertex) is seated in a specific arrangement (adjacency matrix). To find out who sits next to a particular student, you'd just look up that student's position in the seating chart (row), checking who is nearby.

We systematically expand the set of neighbors we can reach one level at a time.

To explore paths from a source vertex (starting point), we look at its neighbors, then the neighbors of those neighbors, marking each visited vertex. This process continues until we reach the target vertex (destination) or exhaust all possibilities.

Think of it like navigating through a maze. You start at one entrance (source), explore all immediately surrounding paths (neighbors), and each time you find a new path, you explore further, until you either find the exit (target) or run out of paths to take.

We need to keep track of the vertices that have been visited.

To avoid revisiting the same vertices and thus becoming stuck in loops, algorithms maintain a record of which vertices have already been explored. This ensures efficient pathfinding without unnecessary repetition.

Picture a tourist exploring a city. To ensure they don’t revisit the same places repeatedly, they might keep a checklist of all the attractions they’ve already visited, thereby making their tour efficient.

There are two fundamental strategies to solve this problem: breadth-first search and depth-first search.

There are two popular methods for searching paths in graphs. Breadth First Search (BFS) explores all neighbors of a vertex before moving deeper into the graph, while Depth First Search (DFS) goes as deep as possible down one path before backtracking to explore others.

If BFS is like a gardener watering all the plants in a row before moving to the next row, DFS is akin to digging deeply into one garden patch to ensure it’s thoroughly watered before moving on. Both ensure the garden gets cared for, but they have different approaches.

These two representations have their advantages and disadvantages.

An adjacency matrix uses a two-dimensional array where the presence of an edge is recorded as '1' and absence as '0'. An adjacency list, on the other hand, maintains a list for each vertex that directly mentions its neighbors. Each representation is better suited for different types of graph operations.

Imagine you’re trying to keep track of your friends. An adjacency matrix is like a massive chart where each friend lists every other friend they know (quantitative but inefficient), while an adjacency list is concise and simple: each friend only lists their immediate connections (efficient for direct queries).

--