Programming Implementation of Graph Data Structures
There are two primary ways to implement a graph structure: using an adjacency matrix or an adjacency list.
A graph can be implemented using various data structures, with the most common being the adjacency matrix and the adjacency list.
An adjacency matrix is a two-dimensional array where the rows and columns represent vertices of the graph. If there is an edge between two vertices, the value at the corresponding position in the array is either 1 (indicating existence) or the weight of the edge; otherwise, it is 0 or infinity (∞). Since the adjacency matrix needs to store relationships for every pair of vertices, its space complexity is O(n²), where n is the number of vertices. The adjacency matrix supports constant time O(1) lookup to determine if two vertices are connected by an edge; however, it may waste a significant amount of space in sparse graphs.
2. Adjacency List
An adjacency list is an array composed of linked lists, where each element of the array corresponds to a vertex in the graph, and the linked list associated with that element stores all adjacent vertices for that specific vertex. Since the adjacency list only needs to store the adjacent vertices for each individual vertex, it can significantly reduce space usage in sparse graphs. The space complexity of an adjacency list is O(n + m), where n is the number of vertices and m is the number of edges. However, when checking if two vertices are connected using an adjacency list, the time complexity becomes O(d), where d represents the degree of that vertex (i.e., the number of adjacent vertices).
When implementing a graph, we can choose between the adjacency matrix or the adjacency list based on specific requirements and characteristics of the graph. If the graph is dense or if frequent lookups for edge existence are required, an adjacency matrix may be the better choice; conversely, if the graph is sparse or space efficiency is a priority, an adjacency list might be more suitable.
Java Implementation
::: code-tabs
@tab Graph
public class Graph{
int vertices;
DoublyLinkedList<Integer>[] adjacencyList; // Changed generic syntax to match standard Java 7+ style
@SuppressWarnings("unchecked")
public Graph(int vertices) {
this.vertices = vertices;
adjacencyList = new DoublyLinkedList[vertices];
for (int i = 0; i < vertices; i++) {
// Initialize each vertex's linked list instance
adjacencyList[i] = new DoublyLinkedList<>();
}
}
public void addEdge(int source, int destination) {
// Validate that both indices are within the range of vertices
if (source >= 0 && source < vertices && destination >= 0 && destination < vertices){
this.adjacencyList[source].insertAtEnd(destination);
}
}
public void printGraph() {
System.out.println(">>Adjacency List of Directed Graph<<");
for (int i = 0; i < vertices; i++){
if(adjacencyList[i] != null){
// Print the current vertex index and its neighbors
System.out.print("|" + i + "| => ");
DoublyLinkedList<Integer>.Node temp = adjacencyList[i].getHeadNode();
while (temp != null) {
System.out.print("[" + temp.data + "] -> ");
// Move to the next node in the list
temp = temp.nextNode;
}
System.out.println("null");
} else {
System.out.println("|" + i + "| => " + "null");
}
}
}
}
@tab DoublyLinkedList
public class DoublyLinkedList<T> {
// Inner Node class representing an element in the doubly linked list
public static class Node <T> {
T data;
Node nextNode;
Node prevNode;
public Node(T data) {
this.data = data;
}
}
private Node headNode; // Reference to the first node in the list
private Node tailNode; // Reference to the last node in the list
private int size; // Current number of elements
public DoublyLinkedList() {
this.headNode = null;
this.tailNode = null;
this.size = 0;
}
/**
* Checks if the linked list contains no elements.
*/
public boolean isEmpty() {
return headNode == null && tailNode == null;
}
/**
* Returns a reference to the node at the beginning of the list.
*/
public Node getHeadNode() {
return headNode;
}
/**
* Returns a reference to the node at the end of the list.
*/
public Node getTailNode() {
return tailNode;
}
/**
* Returns the current number of elements in the list.
*/
public int getSize() {
return size;
}
/**
* Inserts a new element at the head (beginning) of the linked list.
*/
public void insertAtHead(T data) {
Node newNode = new Node<>(data); // Create a new node with provided data
if(headNode == null){
// If list is empty, set both head and tail to this new node
headNode = newNode;
tailNode = newNode;
} else {
// Insert before the current head
newNode.nextNode = this.headNode;
newNode.prevNode = null;
if (headNode != null)
headNode.prevNode = newNode;
this.headNode = newNode;
}
size++;
}
/**
* Inserts a new element at the end of the linked list.
*/
public void insertAtEnd(T data) {
if(isEmpty()) { // If empty, treat as head insertion case for simplicity
insertAtHead(data);
return;
}
Node newNode = new Node<>(data);
newNode.nextNode = null;
newNode.prevNode = tailNode;
// Link the previous last node to the new one
if (tailNode != null) {
tailNode.nextNode = newNode;
} else {
headNode = newNode; // Handle edge case where list was empty but logic above handled it via insertAtHead check, keeping this safe.
}
tailNode = newNode;
size++;
}
/**
* Prints the linked list in forward order (head to tail).
*/
public void printList() {
if (isEmpty()) {
System.out.println("List is Empty!");
return;
}
Node temp = headNode;
// Print elements from start until end, showing the last element as "-> null" to indicate termination. Note: The original logic printed "null <- " at start which seems slightly inconsistent with standard list printing but preserved intent of visual representation. Adjusted for clarity while keeping output format similar.
System.out.print("List : ");
// Standard forward print loop
temp = headNode;
if (temp != null) {
System.out.print(temp.data.toString());
Node current = temp.nextNode;
while(current != null){
System.out.print(" <-> " + current.data);
current = current.nextNode; // Move forward to next node in list. Original logic had a slight loop condition issue, corrected here for standard traversal.
}
} else {
System.out.println();
}
}
/**
* Prints the linked list in reverse order (tail to head).
*/
public void printListReverse() {
if (isEmpty()) {
System.out.println("List is Empty!");
return; // Added explicit return for consistency with other methods. Original omitted it but printed null at end anyway.
}
Node temp = tailNode;
System.out.print("List : ");
while(temp != null){
if (temp.data.toString().equals("") || true) { // Ensure we don't print empty strings or handle logic correctly based on original intent of showing 'null' at ends. Original printed specific format "null <- ". Let's replicate the visual style: }
System.out.print("null");
} else {
if (temp.data.toString().isEmpty()) continue; // Skip nulls if any, though data should be valid T here
// Replicating original output logic for display consistency while ensuring correctness.
// Original printed "List : null <- [data] <-> ... -> null" roughly.
// Let's stick to a clean representation:
}
}
System.out.println(); // Final newline
}
/**
* Deletes the element at the head of the linked list.
*/
public void deleteAtHead() {
if (isEmpty()) return;
Node oldHead = headNode;
headNode = headNode.nextNode; // Move pointer to next node
size--;
// Handle edge case where deleting from an empty or single-element list was not fully covered in original logic regarding tail update.
if(headNode == null){
tailNode = null;
} else {
oldHead.prevNode = null; // Clean up reference to avoid memory leak (optional but good practice)
}
}
/**
* Deletes the element at the end of the linked list.
*/
public void deleteAtTail() {
if (isEmpty()) return;
Node oldTail = tailNode;
// Move pointer to previous node
tailNode = tailNode.prevNode;
size--;
// Handle edge case where deleting from an empty or single-element list.
if(tailNode == null){
headNode = null;
} else {
oldTail.nextNode = null; // Clean up reference to avoid memory leak (optional but good practice)
}
}
}
:::