## Introduction

A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as **Vertices**, and the links that connect the vertices are called **Edges**. It consists of following two components:

- A finite set of vertices also called as nodes.
- A finite set of ordered pair of the form (u, v) called as edge.

Pair of form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost.

## Representations

Representation of a graph largely depends on the operations we intend to support. A graph can be represented using

- Adjacency Matrix
- Incidence Matrix
- Adjacency List

### Adjacency Matrix

Graph is represented using a matrix of size total number of vertices by total number of vertices. So a graph with 4 vertices can be represented using a matrix of 4×4. In this matrix, rows and columns both represents vertices. This matrix is filled with either 1 or 0. 1 represents there is an edge from row vertex to column vertex and 0 represents there is no edge from row vertex to column vertex. An undirected graph the matrix is symmetric and 0 along the diagonal. Directed graphs can have 1s in arbitrary positions, ad its not symmetric along diagonal.

Let the 2D array be adj[][], adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.

// Graph representation using array of ArrayList public class Graph{ private int v; private ArrayList<ArrayList<Integer>> adj; // Initialize the Graph with number of vertices public Graph(int v) { this.v = v; adj = new ArrayList<ArrayList<Integer>>(); for (int i = 0; i < v; i++) { adj.add(new ArrayList<Integer>()); } } // Add an edge between node u and v void addEdge(int u, int v){ adj.get(u).add(v); } }

Removing an edge takes O(1) time. Queries like whether there is an edge from vertex ‘u’ to vertex ‘v’ are efficient and can be done O(1). Consumes more space O(V^2), even if the graph is sparse(contains less number of edges). Adding a vertex is O(V^2) time.

### Incidence Matrix

Graph is represented using a matrix of size total number of vertices by total number of edges. In this matrix, rows represents vertices and columns represents edges. This matrix is filled with either 0 or 1 or -1. Here, 0 represents row edge is not connected to column vertex, 1 represents row edge is connected as outgoing edge to column vertex and -1 represents row edge is connected as incoming edge to column vertex.

### Adjacency List

An array of linked lists is used. Size of the array is equal to number of vertices. Let the array be array[]. An entry array[i] represents the linked list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be stored in nodes of linked lists.

// Graph representation using array of LinkedList public class Graph{ private int v; private LinkedList<integer> adj[]; // Initialize the Graph with number of vertices public Graph(int v) { this.v = v; adj = new LinkedList[v]; for (int i = 0; i < v; i++) { adj[i] = new LinkedList<Integer>(); } } // Add an edge between node u and v void addEdge(int u, int v){ adj[u].add(v); } } // Graph representation using HashMap // HashMap keys represent the node and the values are the lists of neighbors. Map<Integer, List<Integer>> adjList = new HashMap<Integer, List<Integer>>(); adjList.put(0, Arrays.asList(1)); adjList.put(1, Arrays.asList(0, 2)); adjList.put(2, Arrays.asList(1, 0)); adjList.put(3, Arrays.asList(1, 2));

## Reference

Graph