Adjacency List

In this tutorial, you will learn what an adjacency list is. Additionally, you will discover working instances of adjacency list in C, C++, Java, and Python.

An adjacency list addresses a graph as an array of linked lists.

The index of the array addresses a vertex and every element in its linked list addresses the other vertices that structure an edge with the vertex.

In AdjacencyList, we use an array of a list to represent the graph.

The list size is equivalent to the number of vertex(n).

Let’s assume the list of size n as Adjlist[n]

Adjlist[0] will have all the nodes which are associated with vertex 0.

Adjlist[1] will have all the nodes which are associated with vertex 1, etc.

---

Adjacency List representation

A graph and its identical adjacencylist representation appear beneath.

• 

An adjacency list is proficient in terms of storage since we just need to store the values for the edges. For a sparse graph with a huge number of vertices and edges, this can mean a lot of saved space.

---

Adjacency List Structure

The most straightforward adjacency list needs node data structure to store a vertex and graph data structure to coordinate the nodes.

We stay near the fundamental meaning of a graph – an assortment of vertices and edges {V, E}. For simplicity, we use an unlabeled graph rather than a named one for example the vertices are recognized by their files 0,1,2,3.

Let’s dig into the data structures at play here.

struct node
{
    int vertex;
    struct node* next;
};

struct Graph
{
    int numVertices;
    struct node** adjLists;
};

Try not to let the struct node** adjLists overwhelm you.

All we are saying is we need to store a pointer to struct node*. This is on the grounds that we don’t have a clue the number of vertices the graph will have thus we can’t create an array of Linked Lists at compile time.

---

Adjacency List C++

It is a similar structure however by using the in-built list STL data structures of C++, we make the structure a piece cleaner. We are additionally ready to abstract the details of the usage.

class Graph
{
    int numVertices;
    list<int> *adjLists;
    
public:
    Graph(int V);
    void addEdge(int src, int dest);
};

---

Adjacency List Java

We use Java Collections to store the Array of Linked Lists.

class Graph
{
    private int numVertices;
    private LinkedList<integer> adjLists[];
}

The sort of LinkedList is determined by what data you need to store in it. For a labeled graph, you could store a dictionary rather than an Integer

---

Adjacency List Python

There is an explanation Python gets such a lot of affection. A straightforward dictionary of vertices and its edges is a sufficient representation of a graph. You can make the vertex itself as complex as you need.

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

---

Python, Java, and C/C++ Examples

Python

# Adjascency List representation in Python


class AdjNode:
    def __init__(self, value):
        self.vertex = value
        self.next = None


class Graph:
    def __init__(self, num):
        self.V = num
        self.graph = [None] * self.V

    # Add edges
    def add_edge(self, s, d):
        node = AdjNode(d)
        node.next = self.graph[s]
        self.graph[s] = node

        node = AdjNode(s)
        node.next = self.graph[d]
        self.graph[d] = node

    # Print the graph
    def print_agraph(self):
        for i in range(self.V):
            print("Vertex " + str(i) + ":", end="")
            temp = self.graph[i]
            while temp:
                print(" -> {}".format(temp.vertex), end="")
                temp = temp.next
            print(" \n")


if __name__ == "__main__":
    V = 5

    # Create graph and edges
    graph = Graph(V)
    graph.add_edge(0, 1)
    graph.add_edge(0, 2)
    graph.add_edge(0, 3)
    graph.add_edge(1, 2)

    graph.print_agraph()

Java

// Adjascency List representation in Java

import java.util.*;

class Graph {

  // Add edge
  static void addEdge(ArrayList<ArrayList<Integer>> am, int s, int d) {
    am.get(s).add(d);
    am.get(d).add(s);
  }

  public static void main(String[] args) {

    // Create the graph
    int V = 5;
    ArrayList<ArrayList<Integer>> am = new ArrayList<ArrayList<Integer>>(V);

    for (int i = 0; i < V; i++)
      am.add(new ArrayList<Integer>());

    // Add edges
    addEdge(am, 0, 1);
    addEdge(am, 0, 2);
    addEdge(am, 0, 3);
    addEdge(am, 1, 2);

    printGraph(am);
  }

  // Print the graph
  static void printGraph(ArrayList<ArrayList<Integer>> am) {
    for (int i = 0; i < am.size(); i++) {
      System.out.println("\nVertex " + i + ":");
      for (int j = 0; j < am.get(i).size(); j++) {
        System.out.print(" -> " + am.get(i).get(j));
      }
      System.out.println();
    }
  }
}

C

// Adjascency List representation in C

#include <stdio.h>
#include <stdlib.h>

struct node {
  int vertex;
  struct node* next;
};
struct node* createNode(int);

struct Graph {
  int numVertices;
  struct node** adjLists;
};

// Create a node
struct node* createNode(int v) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->vertex = v;
  newNode->next = NULL;
  return newNode;
}

// Create a graph
struct Graph* createAGraph(int vertices) {
  struct Graph* graph = malloc(sizeof(struct Graph));
  graph->numVertices = vertices;

  graph->adjLists = malloc(vertices * sizeof(struct node*));

  int i;
  for (i = 0; i < vertices; i++)
    graph->adjLists[i] = NULL;

  return graph;
}

// Add edge
void addEdge(struct Graph* graph, int s, int d) {
  // Add edge from s to d
  struct node* newNode = createNode(d);
  newNode->next = graph->adjLists[s];
  graph->adjLists[s] = newNode;

  // Add edge from d to s
  newNode = createNode(s);
  newNode->next = graph->adjLists[d];
  graph->adjLists[d] = newNode;
}

// Print the graph
void printGraph(struct Graph* graph) {
  int v;
  for (v = 0; v < graph->numVertices; v++) {
    struct node* temp = graph->adjLists[v];
    printf("\n Vertex %d\n: ", v);
    while (temp) {
      printf("%d -> ", temp->vertex);
      temp = temp->next;
    }
    printf("\n");
  }
}

int main() {
  struct Graph* graph = createAGraph(4);
  addEdge(graph, 0, 1);
  addEdge(graph, 0, 2);
  addEdge(graph, 0, 3);
  addEdge(graph, 1, 2);

  printGraph(graph);

  return 0;
}

C++

// Adjascency List representation in C++

#include <bits/stdc++.h>
using namespace std;

// Add edge
void addEdge(vector<int> adj[], int s, int d) {
  adj[s].push_back(d);
  adj[d].push_back(s);
}

// Print the graph
void printGraph(vector<int> adj[], int V) {
  for (int d = 0; d < V; ++d) {
    cout << "\n Vertex "
       << d << ":";
    for (auto x : adj[d])
      cout << "-> " << x;
    printf("\n");
  }
}

int main() {
  int V = 5;

  // Create a graph
  vector<int> adj[V];

  // Add edges
  addEdge(adj, 0, 1);
  addEdge(adj, 0, 2);
  addEdge(adj, 0, 3);
  addEdge(adj, 1, 2);
  printGraph(adj, V);
}

---

Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.

Graph-based DSA