Member-only story
How to Implement Graphs in Python
A graph is a structure used to represent how two or more objects connect to each other. Many problems in the computer science realm use graph representation, and as such, many algorithms revolve around efficiently finding properties in graphs. Before learning graph algorithms, it is important to understand what a graph is, and how it can be represented in code.
A graph consists of a set of vertices (or nodes), typically referred to as V, as well as a set of edges, typically referred to as E. Consider the graph below.
This graph has 4 vertices, labelled as A,B,C and D. We can therefore define the vertex set as the set containing all of the vertices in the graph, V={A,B,C,D}. The lines connecting the vertices are the edges of the graph, which we typically represent as a set of unordered pairs. For instance, there is an edge between the vertices D and C, which we represent as {D,C}. We can define the edge set as the set containing all edges in the graph, E={{D,B},{D,C},{B,A},{C,A}}. We can think of edges like a connection between two vertices. Through this connection, we can start at one vertex and follow the edge to the next vertex. In this graph, you can freely move from D to B, as well as from B to D. Since the edge has no direction, we call the graph undirected.
To contrast this idea, let’s consider a graph where the edges do have a direction, known as a directed graph. When a graph is directed, we use ordered pairs to indicate the connections between vertices. For instance, suppose we have a similar graph to our undirected example, where V={A,B,C,D}. We can then defined some edges for this graph, E={(B,D),(C,D),(A,B),(A,C)}. The ordered pairs indicated that the edge moves from the first vertex to the second. For example, there is an edge from B to D in our graph, however there is not an edge from D to B.
We indicate direction in our drawings by adding an arrow in the direction that the edge moves in. Below is an example of how we would draw our directed graph.
Sometimes, there may be multiple connections between two vertices in our graph. Consider if we were modelling towns and roads that lead to them. In most cases, a town will have more than one road that leads towards it. If this is the case, we will have multiple edges between the towns. This is represented…
