A simple and effective way to grow your computer science skills is to master the basics. Knowing the basics sets apart the great coders from the merely intermediate ones.

One such basic area in computer science is ** graph theory**, a specific subproblem of which—the pathfinder algorithm—we’ll address in this tutorial. So first things first:

Table of Contents

**What Is a Graph?**

You may already know data structures like lists, sets, and dictionaries. These data structures are denoted as complex data structures–not because they’re difficult to understand but because they build upon other data structures.

A graph is just another complex data structure for relational data.

Relational data consists of edges and vertices. Each vertex stands in one or more relations with other vertices. An example for relational data is the Facebook social graph. Facebook represents users as vertices and friendship relations as edges. Two users are connected via an edge in the graph if they are (Facebook) friends.

**What is a graph?** A graph is a basic data structure in computer science. It models relationships between data items. Using graphs to model real-world phenomena is not a new idea. In 1736, Leonhard Euler has invented the graph data structure to solve the problem of “seven bridges of Königsberg”. Graphs existed way before the first computer was even an idea. In fact, as we will see in this article, graphs helped to make the computer possible. Without graphs, there wouldn’t be a computer as we now know it today.

## How to Represent a Graph Data Structure in the Code?

In this tutorial, we’ll use an adjacency matrix as graph data structure `G`

. Each row `i`

in the matrix stores the out-neighbors of vertex `i`

. And each column `j`

stores the in-neighbors of vertex `j`

. Thus, there is an edge from vertex `i`

to vertex `j`

, if `G[i][j]==1`

.

You can see an example of the adjacency matrix graph representation in the following code of the Pathfinder algorithm:

## The Pathfinder Algorithm in Python

How to determine whether there is a path between two vertices?

The function `find_path(graph, v_start, v_end, path_len)`

checks whether there is a direct or indirect path between two vertices `v_start`

and `v_end`

in graph. We know that there is a direct path between `v_start`

and `v_end`

if both are already neighbors, i.e., `graph[v_start][v_end]==1`

.

def find_path(graph, v_start, v_end, path_len=0): '''Is there a path between vertex v_start and vertex v_end?''' # Traverse each vertex only once if path_len >= len(graph): return False # Direct path from v_start to v_end? if graph[v_start][v_end]: return True # Indirect path via neighbor v_nbor? for v_nbor, edge in enumerate(graph[v_start]): if edge: # between v_start and v_nbor if find_path(graph, v_nbor, v_end, path_len + 1): return True # No direct or indirect path found return False # The graph represented as adjancy matrix G = [[1, 1, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 1, 1, 1, 0], [1, 0, 0, 1, 1]] print(find_path(graph=G, v_start=3, v_end=0)) # False print(find_path(G, 3, 1)) # True

However, even if there is not a direct path, there could be an indirect path between vertices `v_star`

t and `v_end`

. To check this, the algorithm uses a recursive approach. Specifically, there is an indirect path if a vertex `v_nbor`

exists such that there is a path:

v_start --> v_nbor --> ... --> v_end.

The variable `path_len`

stores the length of the current path. We increment it in each recursion level as the current path length increases by one. Note that all paths with length `>=n`

consist of at least `n`

vertices. In other words, at least one vertex is visited twice and a cycle exists in this recursion instance. Hence, we skip recursion for paths with length greater than or equal to the number of vertices in the graph.

In the code snippet, we check whether there is a path between 3 and 0. If you understand what the code is doing, it suffices to look at the adjacency matrix `G`

. There is a direct path from vertex 3 to vertices 1 and 2 (and to itself). But neither vertex 1 nor 2 has any out-neighbors. Therefore, there is no path from vertex 3 to any other vertex (besides vertices 1 and 2).

## Related Video

While working as a researcher in distributed systems, Dr. Christian Mayer found his love for teaching computer science students.

To help students reach higher levels of Python success, he founded the programming education website Finxter.com. He’s author of the popular programming book Python One-Liners (NoStarch 2020), coauthor of the Coffee Break Python series of self-published books, computer science enthusiast, freelancer, and owner of one of the top 10 largest Python blogs worldwide.

His passions are writing, reading, and coding. But his greatest passion is to serve aspiring coders through Finxter and help them to boost their skills. You can join his free email academy here.