Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in Java

Graph Implementation

Explore how to implement a directed graph in Java by using an adjacency list represented with linked lists. Understand the structure and methods of the Graph class, including vertex storage, edge addition with efficient insertion, and how to print the graph. Learn practical graph construction to prepare for coding interviews.

We'll cover the following...

Introduction #

In this lesson, we will implement a Directed Graph in java using an Adjacency List.

Structure of Graph Class #

Graph class consists of two data members: a total number of vertices in the graph, and an array of the linked list to store the adjacency list of vertices. Below is a code snippet of our Graph class:

Java
public class Graph{
    int vertices; //Total number of vertices in graph
    DoublyLinkedList<Integer> adjacencyList[]; //An array of linked lists to store adjacent vertices.
    
    void printGraph(); //Prints Graph (Adjaceny List)
    void addEdge(int source,int destination); //Adds an Edge from source vertex to destination vertex
}

Note: We are using a Doubly Linked list with Tail for the adjacency list implementation in the Graph class. The purpose of using a DLL with Tail is that the insertAtEnd() operation has O(1) ...