**What is Graph:**

*G = (V,E)*

Graph is a collection of nodes or vertices (V) and edges(E) between them. We can traverse these nodes using the edges. These edges might be weighted or non-weighted.

There can be two kinds of Graphs

- Un-directed Graph – when you can traverse either direction between two nodes.
- Directed Graph – when you can traverse only in the specified direction between two nodes.

Now how do we represent a Graph, There are two common ways to represent it:

- Adjacency Matrix
- Adjacency List

**Adjacency Matrix:**

Adjacency Matrix is 2-Dimensional Array which has the size VxV, where V are the number of vertices in the graph. See the example below, the Adjacency matrix for the graph shown above.

adjMaxtrix[i][j] = 1 when there is edge between Vertex i and Vertex j, else 0.

It’s easy to implement because removing and adding an edge takes only O(1) time.

But the drawback is that it takes O(V^{2}) space even though there are very less edges in the graph.

**Adjacency List:**

Adjacency List is the Array[] of Linked List, where array size is same as number of Vertices in the graph. Every Vertex has a Linked List. Each Node in this Linked list represents the reference to the other vertices which share an edge with the current vertex. The weights can also be stored in the Linked List Node.

The code below might look complex since we are implementing everything from scratch like linked list, for better understanding. Read the articles below for easier implementations (Adjacency Matrix and Adjacency List)

- Graph Implementation – Adjacency Matrix
- Graph Implementation – Adjacency List – Better
- Weighted Graph Implementation

**Complete Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class GraphRersentation { | |

public static void main(String args[]) { | |

Graph gph = new Graph(5); | |

gph.addEdge(0, 1); | |

gph.addEdge(0, 2); | |

gph.addEdge(0, 3); | |

gph.addEdge(1, 2); | |

gph.addEdge(2, 4); | |

gph.printGraph(gph); | |

} | |

} | |

// Create adjacency node | |

class adjNode { | |

int source; | |

int destination; | |

adjNode next; | |

public adjNode(int source, int destination) { | |

this.source = source; | |

this.destination = destination; | |

next = null; | |

} | |

} | |

class adjList { | |

adjNode head; | |

} | |

class Graph { | |

int V; | |

adjList array[]; | |

// constructor of graph, initialize the number of vertex in graph | |

// and create those many adjacency lists and initialize all heads to null | |

public Graph(int V) { | |

this.V = V; | |

array = new adjList[V]; | |

for (int i = 0; i < V; i++) { | |

array[i] = new adjList(); | |

array[i].head = null; | |

} | |

} | |

public void addEdge(int source, int destination) { | |

// first create a forward edge source -> destination | |

adjNode adn = new adjNode(source, destination); | |

// add this node to the source adj List | |

adn.next = array[source].head; | |

array[source].head = adn; | |

// now create a reverse edge since its a undirected graph | |

// adn = new adjNode(source); | |

// adn.next = array[destination].head; | |

// array[destination].head = adn; | |

} | |

public void printGraph(Graph gph) { | |

int vertex = gph.V; | |

adjNode ad; | |

for (int i = 0; i < vertex; i++) { | |

ad = gph.array[i].head; | |

if(ad!=null){ | |

System.out.println("\nNodes connected to Vertex " + ad.source | |

+ " are :"); | |

while (ad != null) { | |

System.out.print(" " + ad.destination); | |

ad = ad.next; | |

} | |

} | |

} | |

} | |

} |

**Output**:

Nodes connected to Vertex 0 are : 3 2 1 Nodes connected to Vertex 1 are : 2 Nodes connected to Vertex 2 are : 4