One of the simplest ways to represent graphs is through edge lists. In this method, a graph is represented by listing all its edges, where each edge contains two values which denote a connection between the corresponding pair of nodes or vertices.
Representing Un-Directed Graph Using Edge List
Let’s consider the example un-directed graph below and represent it programmatically using edge list.
This is the representation of the above graph using edge list:
# Declare the set of vertices that make up the graph
vertices = ['A', 'B', 'C', 'D', 'E', 'F']
# Now declare the list of edges that make up the graph
edge_list = [['A','B'], ['A','C'], ['B','C'], ['B','D'], ['C','E'], ['C','F']]
Since the edges are bi-directional in an undirected graph, both the edges [A,B] and [B,A] convey the same meaning and including only one of them is sufficient.
Also the reason why we also store list of all the nodes/vertices is because not all the nodes are connected to the graph. There could be some nodes which are isolated while still being part of the graph. In this case, the edge list doesn’t contain the isolated node and this is when the vertices set is useful. Below is one such graph:
Node G will be included in the vertices list but it won’t be present in the edge list as there are no edges from/to node G.
Representing Directed Graph Using Edge List
Let’s consider the example directed graph below and represent it programmatically using edge list.
This is the representation of the above graph using edge list:
# Declare the set of vertices that make up the graph
vertices = ['A', 'B', 'C', 'D', 'E', 'F']
# Now declare the list of edges that make up the graph
edge_list = [['A','B'], ['A','C'], ['B','C'], ['C','B'], ['B','D'], ['C','E'], ['C','F']]
Since all the edges are uni-directional in a directed graph, if edge [A,B] exists, it doesn’t mean that edge [B,A] also exists. In the above graph, there are two edges between node B and node C in either direction. This is reflected in the edge list representation by including both the edges [B,C] and [C,B].
Pros and Cons
The edge list representation is straightforward to understand and implement. It clearly shows all the connections in the graph without any additional complexity.
But for graphs with many edges (dense graphs), the edge list can become large and unwieldy, leading to increased memory usage and slower performance. In cases like these, adjacency list or adjacency matrix representation of graphs is more suitable.
Also, finding out if there is an edge between two nodes can be slow since it requires scanning through the entire list of edges, resulting in O(E) time complexity, where E is the number of edges.