Graph Representation

Graphs can be represented in various ways based on the underlying data structure used to store the vertices and edges.

Thank you for reading this post, don't forget to subscribe!

• We introduce four data structures for representing a graph:

• Edge List
• Adjacency List
• Adjacency Map
• Adjacency Matrix

Edge List:

An edge list is a simple and straightforward way to represent a graph in which all vertex objects are stored in an unordered list V, and all edge objects are stored in an unordered list E.

Adjacency List:

An adjacency list is a popular data structure for representing graphs, where the graph is stored as an array of lists.

• Each element in the array represents a vertex in the graph, and the corresponding list contains the vertices that are adjacent to the given vertex.

• This data structure efficiently captures the connections and relationships between vertices in the graph.

For example:-

‣ Adjacency Matrix:

Let G=(V,E) be a graph with n vertices: v₁, v₂, v₃, …… V_n. The adjacency matrix of G with respect to given ordered list of vertices is a nxn matrix denoted by A(G)=(a_ij)_nxn.
such that,

Undirected graph representation

Directed graph represenation

In the above examples, 1 represents an edge from row vertex to column vertex, and 0 represents no edge from row vertex to column vertex.

Q). Find the adjacency matrix M_A of undirected graph G shown in Fig:

Solution:
Since graph G consist of four vertices. Therefore, the adjacency matrix wills a 4 x 4 matrix. The adjacency matrix is as follows in fig: