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.
