Graph Data Structures in Java

Introduction

In this tutorial, you will learn how to create and manipulate graph data structures in Java. Graphs are a fundamental data structure used to represent relationships between objects. We will explore the different types of graphs, how to represent them, and how to implement common operations such as adding and removing vertices and edges, breadth-first search, depth-first search, and more.

Skills Graph

Create a Node Class

First, we'll create a Node class to represent vertices in the graph. Each node will have a name and possibly other information, such as a value or weight.

public class Node {
    private String name;

    public Node(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }
}

Create a Graph Class

Next, we'll create a Graph class to represent the graph itself. We'll use an adjacency list to store edges and their endpoints.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Graph {
    private Map<Node, List<Node>> adjacencyList;

    public Graph() {
        this.adjacencyList = new HashMap<>();
    }

    public void addNode(Node node) {
        adjacencyList.putIfAbsent(node, new ArrayList<>());
    }

    public void addEdge(Node node1, Node node2) {
        adjacencyList.get(node1).add(node2);
        adjacencyList.get(node2).add(node1);
    }

    public void removeNode(Node node) {
        adjacencyList.values().stream().forEach(e -> e.remove(node));
        adjacencyList.remove(node);
    }

    public void removeEdge(Node node1, Node node2) {
        List<Node> list1 = adjacencyList.get(node1);
        List<Node> list2 = adjacencyList.get(node2);
        if (list1 != null) {
            list1.remove(node2);
        }
        if (list2 != null) {
            list2.remove(node1);
        }
    }

    public List<Node> getNeighbors(Node node) {
        return adjacencyList.get(node);
    }
}

Create a Graph

Now, let's create a graph and add some nodes and edges.

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");

graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addNode(nodeD);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);
graph.addEdge(nodeC, nodeD);
graph.addEdge(nodeD, nodeA);

Breadth-First Search

We'll now implement a breadth-first search algorithm to traverse the nodes in the graph in breadth-first order.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class BreadthFirstSearch {
    public List<Node> bfs(Graph graph, Node start) {
        List<Node> visited = new ArrayList<>();
        Deque<Node> queue = new ArrayDeque<>();
        visited.add(start);
        queue.add(start);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            List<Node> neighbors = graph.getNeighbors(node);
            for (Node neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }

        return visited;
    }
}

Example of how to run:

javac Graph.java BreadthFirstSearch.java Node.java && java BreadthFirstSearch

Depth-First Search

We'll now implement a depth-first search algorithm to traverse the nodes in the graph in depth-first order.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DepthFirstSearch {
    public List<Node> dfs(Graph graph, Node start) {
        List<Node> visited = new ArrayList<>();
        dfsHelper(graph, start, visited, new HashSet<>());
        return visited;
    }

    private void dfsHelper(Graph graph, Node current, List<Node> visited, Set<Node> seen) {
        visited.add(current);
        seen.add(current);
        for (Node neighbor : graph.getNeighbors(current)) {
            if (!seen.contains(neighbor)) {
                dfsHelper(graph, neighbor, visited, seen);
            }
        }
    }
}

Example of how to run:

javac Graph.java DepthFirstSearch.java Node.java && java DepthFirstSearch

Delete a Node

We can remove a node from the graph and also remove any edges connected to that node.

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");

graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addNode(nodeD);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);
graph.addEdge(nodeC, nodeD);
graph.addEdge(nodeD, nodeA);

graph.removeNode(nodeC);

Delete an Edge

We can remove an edge between two nodes in the graph.

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");

graph.addNode(nodeA);
graph.addNode(nodeB);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);

graph.removeEdge(nodeA, nodeB);

Summary

In this tutorial, we learned how to create a graph data structure in Java using a node and adjacency list representation. We also implemented operations to manipulate the graph, including adding and removing nodes and edges. Finally, we implemented two search algorithms: breadth-first search and depth-first search.