Data Structure & Algorithm in Java

  1. Home
  2. Docs
  3. Data Structure & Alg...
  4. Graphs
  5. Graph Representation

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

Adjacency List:

image 45
image 46
Screenshot 2024 02 22 131703

‣ Adjacency Matrix:

Let G=(V,E) be a graph with n vertices: v1, v2, v3, …… Vn. The adjacency matrix of G with respect to given ordered list of vertices is a nxn matrix denoted by A(G)=(aij)nxn.
such that,

image 112

Undirected graph representation

image 109

Directed graph represenation

image 110

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 MA of undirected graph G shown in Fig:

image 114

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:

image 115

How can we help?

Leave a Reply

Your email address will not be published. Required fields are marked *