Java Data Structures and Algorithms for Beginners

Graph Data Structure

Definition and Concepts

A graph is a non-linear data structure consisting of nodes (also called vertices) connected by edges. Graphs can represent relationships between entities, where nodes represent entities and edges represent connections. Graphs can be directed (edges have direction, like one-way roads) or undirected (edges are bidirectional, like friendships). They can also be weighted (edges have values, like distances) or unweighted. A common representation is an adjacency list, where each node stores a list of its adjacent nodes. You can visualize a graph as a network of cities (nodes) connected by roads (edges). Graphs are versatile and used to model complex relationships in various applications.

Why Use It?

Graphs are used to model and analyze relationships between entities, enabling solutions to problems like finding shortest paths, detecting cycles, or determining connectivity. They provide a flexible framework for representing networks, making them essential for applications in computer science, social networks, and logistics. Graphs support efficient algorithms for traversal, pathfinding, and optimization, with time complexities depending on the representation and algorithm used.

Where to Use? (Real-Life Examples)

• Social Networks: Social media platforms use graphs to represent users (nodes) and friendships or follows (edges) to recommend connections or analyze communities.
• Navigation Systems: GPS applications use graphs to model road networks, with cities as nodes and roads as weighted edges, to compute shortest paths.
• Internet Routing: The internet uses graphs to represent routers and connections, enabling efficient data packet routing.
• Dependency Management: Build tools like Maven use graphs to manage dependencies between software modules, detecting cyclic dependencies.

Explain Operations

• Add Vertex: This operation adds a new node to the graph. It has a time complexity of O(1) in an adjacency list.
• Add Edge: This operation adds a connection between two nodes. It has a time complexity of O(1) for an undirected graph using an adjacency list.
• Remove Vertex: This operation removes a node and all its edges. It has a time complexity of O(V + E), where V is the number of vertices and E is the number of edges.
• Remove Edge: This operation removes a connection between two nodes. It has a time complexity of O(E) in the worst case for an adjacency list.
• Depth-First Search (DFS): This operation traverses the graph by exploring as far as possible along each branch before backtracking. It has a time complexity of O(V + E).
• Breadth-First Search (BFS): This operation traverses the graph level by level, visiting all neighbors of a node before moving to the next level. It has a time complexity of O(V + E).

Java Implementation

The following Java code implements an undirected graph using an adjacency list, with basic operations and DFS/BFS traversals.

import java.util.*;

public class Graph {
    private Map<Integer, List<Integer>> adjList; // Adjacency list to store the graph
    private int vertexCount; // Number of vertices in the graph

    // Constructor to initialize an empty graph
    public Graph() {
        adjList = new HashMap<>();
        vertexCount = 0;
    }

    // Add Vertex: Adds a new vertex to the graph
    public void addVertex(int vertex) {
        if (!adjList.containsKey(vertex)) { // Checks if vertex doesn't already exist
            adjList.put(vertex, new ArrayList<>());
            vertexCount++;
        }
    }

    // Add Edge: Adds an undirected edge between two vertices
    public void addEdge(int vertex1, int vertex2) {
        if (!adjList.containsKey(vertex1) || !adjList.containsKey(vertex2)) {
            throw new IllegalArgumentException("Both vertices must exist in the graph.");
        }
        adjList.get(vertex1).add(vertex2); // Adds vertex2 to vertex1's list
        adjList.get(vertex2).add(vertex1); // Adds vertex1 to vertex2's list (undirected)
    }

    // Remove Vertex: Removes a vertex and all its edges
    public void removeVertex(int vertex) {
        if (!adjList.containsKey(vertex)) {
            throw new IllegalArgumentException("Vertex not found in the graph.");
        }
        List<Integer> neighbors = adjList.get(vertex);
        for (int neighbor : neighbors) { // Removes vertex from neighbors' lists
            adjList.get(neighbor).remove(Integer.valueOf(vertex));
        }
        adjList.remove(vertex); // Removes the vertex
        vertexCount--;
    }

    // Remove Edge: Removes an undirected edge between two vertices
    public void removeEdge(int vertex1, int vertex2) {
        if (!adjList.containsKey(vertex1) || !adjList.containsKey(vertex2)) {
            throw new IllegalArgumentException("Both vertices must exist in the graph.");
        }
        adjList.get(vertex1).remove(Integer.valueOf(vertex2)); // Removes vertex2 from vertex1's list
        adjList.get(vertex2).remove(Integer.valueOf(vertex1)); // Removes vertex1 from vertex2's list
    }

    // Depth-First Search: Traverses the graph starting from a vertex
    public List<Integer> dfs(int startVertex) {
        if (!adjList.containsKey(startVertex)) {
            throw new IllegalArgumentException("Start vertex not found in the graph.");
        }
        List<Integer> result = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        dfsRec(startVertex, visited, result);
        return result;
    }

    private void dfsRec(int vertex, Set<Integer> visited, List<Integer> result) {
        visited.add(vertex); // Marks the vertex as visited
        result.add(vertex); // Adds vertex to result
        for (int neighbor : adjList.get(vertex)) { // Visits unvisited neighbors
            if (!visited.contains(neighbor)) {
                dfsRec(neighbor, visited, result);
            }
        }
    }

    // Breadth-First Search: Traverses the graph starting from a vertex
    public List<Integer> bfs(int startVertex) {
        if (!adjList.containsKey(startVertex)) {
            throw new IllegalArgumentException("Start vertex not found in the graph.");
        }
        List<Integer> result = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        visited.add(startVertex);
        queue.offer(startVertex);
        while (!queue.isEmpty()) {
            int vertex = queue.poll(); // Dequeues a vertex
            result.add(vertex); // Adds vertex to result
            for (int neighbor : adjList.get(vertex)) { // Enqueues unvisited neighbors
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        return result;
    }

    // isEmpty: Checks if the graph is empty
    public boolean isEmpty() {
        return vertexCount == 0;
    }

    // Size: Returns the number of vertices in the graph
    public int size() {
        return vertexCount;
    }
}

How It Works

1. Initialization: The constructor initializes an empty HashMap for the adjacency list and sets vertexCount to 0, indicating an empty graph.
2. Add Vertex: The method adds a new vertex to the adjList with an empty list of neighbors if it doesn’t already exist, incrementing vertexCount.
3. Add Edge: The method adds an undirected edge by appending each vertex to the other’s neighbor list in the adjList, ensuring both vertices exist.
4. Remove Vertex: The method removes the vertex’s neighbor list and removes the vertex from all its neighbors’ lists, then removes the vertex from adjList and decrements vertexCount.
5. Remove Edge: The method removes each vertex from the other’s neighbor list in the adjList, ensuring both vertices exist.
6. Depth-First Search (DFS): The method uses recursion to explore as far as possible along each branch, marking vertices as visited and adding them to the result list.
7. Breadth-First Search (BFS): The method uses a queue to explore nodes level by level, marking vertices as visited, adding them to the result, and enqueuing unvisited neighbors.
8. isEmpty Operation: The method returns true if vertexCount equals 0, indicating an empty graph, and false otherwise.
9. Size Operation: The method returns vertexCount, which represents the number of vertices in the graph.

Complexity Analysis Table

Note: V is the number of vertices, and E is the number of edges. Time complexities assume an adjacency list representation.

Key Differences / Notes

• Adjacency List vs. Adjacency Matrix:
  • The implementation above uses an adjacency list, which is space-efficient (O(V + E)) and suitable for sparse graphs.
  • An adjacency matrix uses O(V²) space and is better for dense graphs or when checking edge existence is frequent.
• Directed vs. Undirected Graphs:
  • The implementation is for an undirected graph. For a directed graph, only add the edge to the source vertex’s neighbor list.
• Weighted Graphs: The implementation is unweighted. For weighted graphs, store edge weights in the adjacency list (e.g., as a Map<Integer, Integer> for weights).
• Thread Safety: The implementation is not thread-safe. For concurrent applications, use Java’s ConcurrentHashMap for the adjacency list or synchronize access.
• Java’s Built-in Support: Java does not provide a direct graph class, but libraries like JGraphT or Guava’s Graph can be used for advanced graph operations.

✅ Tip: Use an adjacency list for sparse graphs to save memory, and an adjacency matrix for dense graphs to optimize edge lookups.

⚠ Warning: Ensure the graph is properly initialized with all vertices before adding edges, as missing vertices can cause errors in adjacency list operations.

Exercises

1. Graph Connectivity: Write a Java program that uses the graph implementation to check if a graph is connected (all vertices reachable from a starting vertex) using DFS or BFS.
2. Cycle Detection: Extend the graph implementation to detect if the graph contains a cycle using DFS. Test it with cyclic and acyclic graphs.
3. Shortest Path (Unweighted): Implement a method to find the shortest path between two vertices in an unweighted graph using BFS. Return the path as a list of vertices.
4. Weighted Graph Extension: Modify the graph implementation to support weighted edges (store weights in the adjacency list). Test it by adding and retrieving edge weights.
5. Social Network Simulation: Create a program that simulates a social network using the graph. Allow users to add users (vertices), friendships (edges), and perform DFS to find mutual friends.