Graph data structure tutorial 3. Graph Representation Adjacency List

In this chapter we shall learn about:

3.1 Introduction
3.2 Representation in Linked List
3.3 Now why do we use Linked List to represent Adjacency Lists?
3.4 Implementation of Graph Representation using Adjacency Lists using C++
3.5 Output

3.1 Introduction:

In the previous chapter we have seen representing graph using Adjacency Matrix. The drawback is that it consumes large amount of space if the number of vertices increases. Hence in this chapter we shall look at more efficient way of representing of the graph, using Adjacency Lists.

3.2 Representation in Linked List

In this representation, we use Linked List for representing the adjacency. For any particular vertex, we create a list of all the vertices it is adjacent to as shown below:

Example:

From the above image, we can say that Vertex “A” is adjacent to vertex “C” “E” “B”.

3.3 Now why do we use Linked List to represent Adjacency Lists?

We can also use arrays to represent the relation. But the problem here is, if there is an additional vertex that has been added, if we are using arrays, all the data has to be deleted. Again the list has to be created from scratch.

But by using Linked List, addition, deletion of a vertex or edge can be easily done.

Now let us see with an example how to represent graph using adjacency lists.

Consider the graph given below

The adjacency matrix will be as shown below:

3.4 Implementation of Graph Representation using Adjacency Lists using C++

#include<iostream>

using namespace std;

// struct for an adjacency list node
// to hold data and next element
struct AdjListNode
{
    int data;
    AdjListNode *next;
};

// struct for an adjacency list

struct AdjList
{
    AdjListNode *head;  //pointer to head node of list
};

//struct for a graph. A graph as an array of adjacency lists

struct Graph
{
    int V;
    AdjList *arr;
};

//create a new node
AdjListNode* newAdjListNode(int data)
{
    AdjListNode *nptr = new AdjListNode;
    nptr->data = data;
    nptr->next = NULL;
    return nptr;
}

//function to create a graph of V - vertices
Graph* createGraph(int V)
{
    Graph *graph = new Graph;
    graph->V = V;
    //create an array of adjacency list. size of array - V
    graph->arr = new AdjList[V];

    //initialize with NULL
    for(int i = 0; i < V; i++)
    {
        graph->arr[i].head = NULL;
    }
    return graph;
}

//add an edge to an undirected Graph
void addEdge(Graph *graph, int src, int dest)
{
    // add an edge from src to dest
    AdjListNode *nptr = newAdjListNode(dest);
    nptr->next = graph->arr[src].head;
    graph->arr[src].head=nptr;

    // as graph is undirected, add an edge from dest to src also
    nptr = newAdjListNode(src);
    nptr->next = graph->arr[dest].head;
    graph->arr[dest].head=nptr;
}

//function to print the graph
void printGraph(Graph* graph)
{
    for(int i=0;i<graph->V;i++)
    {
        AdjListNode *root=graph->arr[i].head;
        cout<<"Adjacency list of vertex "<<i<<endl;

        while(root!=NULL)
        {
            cout<<root->data<<" -> ";
            root=root->next;
        }
        cout<<endl;
    }
}

int main()
{
//create a new graph
    int totalVertices=4;
    Graph *graph;
    graph = createGraph(totalVertices);

    //connect edges
    addEdge(graph,0,3);
    addEdge(graph,0,1);
    addEdge(graph,2,3);
    addEdge(graph,1,3);
    addEdge(graph,2,3);

    printGraph(graph);
}

3.5 Output

Adjacency list of vertex 0

1 -> 3 ->

Adjacency list of vertex 1

3 -> 0 ->

Adjacency list of vertex 2

3 -> 3 ->

Adjacency list of vertex 3

2 -> 1 -> 2 -> 0 ->