Data Structures for Coding Interviews in Java/

...

/

Graph Implementation

Graph Implementation

This lesson will cover the implementation of a directed Graph via the Adjacency List. We will also go through the time complexity of basic graph operations.

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:

Press + to interact
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) ...