Java : Adjacency list implementation for storing graph

Storing graph as an adjacency list using a list of the lists in Java

Below is a simple example of a graph where each node has a number that uniquely identifies it and differentiates it from other nodes in the graph. Such a graph can be stored in an adjacency list where each node has a list of all the adjacent nodes that it is connected to.
An adjacency list can be implemented as a list of lists in Java.

Example : In the below adjacency list we can see
a) Node 0 has a list storing adjacent nodes 1 and 2.
b) Node 1 has a list storing adjacent nodes 0, 3 and 4.


Storing graph using list of lists


Java : Storing graph in an adjacency list. Implemented using list of lists in Java 8

import java.util.List;
import java.util.ArrayList;

class Graph {

    Integer nodes;
    List<List<Integer>> adjlist;

    Graph (Integer arg_nodes) {
        nodes = arg_nodes;
        adjlist = new ArrayList<>(nodes);
        for (int i=0; i<nodes; i++)
            adjlist.add(new ArrayList<>());
    }

    void AddEdge (Integer src, Integer dst) {
        adjlist.get(src).add(dst);
        adjlist.get(dst).add(src);
    }

    void Iterate (Integer src) {
        System.out.print("\n" + src + " : ");
        for(Integer adj_node : adjlist.get(src)) {
            System.out.print(adj_node + " ");
        }
    }
    public static void main (String[] args) {

        Graph g = new Graph(7);
        g.AddEdge(0,1);
        g.AddEdge(0,2);
        g.AddEdge(1,3);
        g.AddEdge(1,4);
        g.AddEdge(2,3);
        g.AddEdge(3,5);
        g.AddEdge(4,6);
        g.AddEdge(5,6);

        System.out.print("Adjacency list implementation for graph");

        g.Iterate (0);
        g.Iterate (1);
        g.Iterate (4);
    }
}

Output

Adjacency list implementation for graph
0 : 1 2
1 : 0 3 4
4 : 1 6

Storing graph as an adjacency list using map and list in Java

Below is an example of a graph where each node has a name (string) and an id (number) that uniquely identifies it and differentiates it from other nodes in the graph. Such a graph can be stored in an adjacency list where each node has a list of all the adjacent nodes that it is connected to.
An adjacency list for such a graph can be implemented as a map of node and list of nodes in Java.

Example : In the below adjacency list we can see
a) Node ( Alfa, 1 ) has a list storing adjacent nodes ( Cod, 2 ), ( Pi, 3 ) and ( Ram , 4)


Storing graph using map


Java : Storing graph in an adjacency list. Implemented using map of string and list of string in Java 8

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

class Graph {

    static class Node {
        String name;
        Integer id;

        Node(String arg_name, Integer arg_id) {
            name = arg_name;
            id   = arg_id;
        }
        void Display() {
            System.out.print(" ( " + name + " , " + id + " )");
        }
    }

    Map<Node, List<Node>> adjlist = new HashMap<Node, List<Node>>();

    void Add_Adjacent_Nodes (Node src, List<Node> adj_nodes) {
        adjlist.put(src, adj_nodes);
    }

    void Iterate (Node src) {
        List<Node> adj_nodes = adjlist.get(src);
        src.Display();
        System.out.print(" : ");
        for (Node node : adj_nodes) {
            node.Display();
        } System.out.print("\n");
    }

    public static void main (String[] args) {
        Node n1 = new Node("Alfa", 1);
        Node n2 = new Node("Cod", 2);
        Node n3 = new Node("Pi", 3);
        Node n4 = new Node("Ram", 4);
        Node n5 = new Node("Yo", 5);

        List<Node> n1_list = Arrays.asList(n2, n3, n4);
        List<Node> n2_list = Arrays.asList(n1, n4);
        List<Node> n3_list = Arrays.asList(n1, n4, n5);
        List<Node> n4_list = Arrays.asList(n1, n2, n3, n5);
        List<Node> n5_list = Arrays.asList(n3, n4);

        System.out.println("Adjacency list implementation for graph");

        Graph g = new Graph();
        g.Add_Adjacent_Nodes (n1, n1_list);
        g.Add_Adjacent_Nodes (n2, n2_list);
        g.Add_Adjacent_Nodes (n3, n3_list);
        g.Add_Adjacent_Nodes (n4, n4_list);
        g.Add_Adjacent_Nodes (n5, n5_list);

        g.Iterate(n1);
        g.Iterate(n2);
        g.Iterate(n3);
        g.Iterate(n4);
    }
}

Output

Adjacency list implementation for graph
( Alfa , 1 ) : ( Cod , 2 ) ( Pi , 3 ) ( Ram , 4 )
( Cod , 2 ) : ( Alfa , 1 ) ( Ram , 4 )
( Pi , 3 ) : ( Alfa , 1 ) ( Ram , 4 ) ( Yo , 5 )
( Ram , 4 ) : ( Alfa , 1 ) ( Cod , 2 ) ( Pi , 3 ) ( Yo , 5 )

Copyright © 2019-2020, Algotree.org.
All rights reserved.