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.
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”.
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:
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); }
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 ->
Further Reading: