Graph data structure can be programmatically represented in various ways, each useful in different scenarios depending on the context and computational requirements. The choice of representation depends on factors like the size of the graph, the density of connections, and the operations to be performed.
Understanding different representations allows programmers and computer scientists to select the most suitable representation based on trade-offs between memory usage, speed of operations, and the nature of the graph structure itself.
Below are some of the common graph representations:
Representing Graph using Edge List
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.
Read More
Representing Graph using Adjacency List
Adjacency lists provide a compact way to represent graphs by grouping and storing all connections from each node. In this representation, each node maintains a list of all the nodes it is connected to.
Representing an Un-Directed Graph Using Adjacency List Let’s consider the example un-directed graph below and represent it programmatically using Adjacency list.
Read More
Representing Graph using Adjacency Matrix
An Adjacency matrix is a type of graph representation which uses a square matrix (two dimensional array of values) to indicate presence of edges. The row index correspond to the node from which an edge starts and column index correspond to node at which an edge ends, and the matrix elements indicate if there’s an edge for a given start and end node.
Read More
Converting between Edge list, Adjacency List and Adjacency Matrices
In graph theory, there are three common ways to represent a graph: edge list, adjacency list, and adjacency matrix. Each representation has its own advantages and disadvantages. Depending on the algorithm being applied on a graph, one representation might be more efficient than another.
Read More