## Introduction

A graph is a non-linear data structure that depicts relationships among the entities. Every graph is a set of points referred to as nodes or vertices, which are connected using edges. The vertices here represent entities in a graph. On the other hand, edges express relationships between entities.

Graphs can broadly be categorized into Undirected or Directed.

An undirected graph with five vertices is illustrated below.

## Representation of Graphs

A graph can be represented using an adjacency matrix and an adjacency list.

There are also other representations like Incidence Matrix and Incidence List, which we will see further in this article. The choice of graph representation is situation-specific. It depends on the type of operations and ease of use.

**Checkout also: **__Application of graph data structure__

### Adjacency Matrix

Adjacency Matrix is a 2D array of size V x V where V represents the number of vertices in a graph. Let the 2D array be adj[][], in that adj[i][j] = 1 indicates that there is an edge going from vertex i to vertex j.

Adjacency Matrix is also used to represent weighted graphs.

Must Read __Difference between ArrayList and LinkedList__

**Example:**

**Consider the following undirected graph representation:**

**Directed graph represenation**

* Pros:* In adjacency, matrix representation is easier to implement and follow.

* Cons:* A lot of space and time is invested in visiting all the neighbors of a vertex, and we have to traverse all the vertices in the graph.

### Incidence Matrix

The incidence matrix A of an undirected graph has a row for each vertex and a column for each graph's edge. The element A[[i,j]] of A is '1' if the ith vertex is a vertex of the jth edge and '0' otherwise.

The incidence matrix A of a directed graph has a row for each vertex and a column for each graph's edge. The element A[[i,j] of A is '− 1' if the ith vertex is an initial vertex of the jth edge, '1' if the ith vertex is a terminal vertex; otherwise, it will be '0'.

This incidence matrix is filled with either 0 or 1 or -1. Where,

- 0 is used to represent a row edge that is not connected to a column vertex.
- 1 is used to represent a row edge connected as the outgoing edge to a column vertex.
- -1 is used to represent a row edge connected as an incoming edge to a column vertex.

**Example for directed graph representation.**

### Adjacency List

In the adjacency list representation of a graph, every vertex is represented as a node. The node may either contain a reference or data to a linked list. This linked list will provide us with a list of all adjacent nodes to the current node.

**Example**

**Adjacency list for the undirected graph.**

List corresponding to node ‘3’ is the maximum having four entries.

* Pros:* Adjacency list enables a faster search process in comparison to adjacency matrix.

Adjacency list saves a lot of space.

* Cons:* It is not the best representation of graphs especially when it comes to adding or removing nodes.

Check out this problem -

__No of Spanning Trees in a Graph__