Graph Representation

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

• 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: