Adjacency List

An array of list is used in Adjacency List. The size of an array is equal to the number of vertices. Let the array be array[]. An entry array[i] represents the list of vertices adjacent to the ‘i’th vertex. This representation can also be used to represent a weighted graph. The weights of edges can be represented as list of pairs. The following is the adjacency list representation of the above graph:

The following is the implementation of Graph, we use dynamic arrays (vector in C++ / ArrayList in Java) to represent adjacency list instead of linked list. The vector implementation has advantages of cache friendliness.

The following is the C implementation of Adjacency list:

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

struct Node
{
    int vertex;
    struct Node* next;
};
struct Node* createNode(int);
struct Graph
{
    int numVertices;
    struct Node** adjLists;
};

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

struct Graph* createGraph(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;
}

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

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

void printGraph(struct Graph* graph)
{
    int v;
    for (v = 0; v < graph->numVertices; v++)
    {
        struct Node* temp = graph->adjLists[v];
        printf("\n Adjacency list of vertex %d\n ", v);
        while (temp)
        {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

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

    printGraph(graph);

    return 0;
}

Adjacency list of vertex 0
 2 -> 1 ->

 Adjacency list of vertex 1
 5 -> 3 -> 4 -> 2 -> 0 ->

 Adjacency list of vertex 2
 4 -> 1 -> 0 ->

 Adjacency list of vertex 3
 4 -> 1 ->

 Adjacency list of vertex 4
 6 -> 3 -> 2 -> 1 ->

 Adjacency list of vertex 5
 6 -> 1 ->