C++ Program to Implement Adjacency List

This C++ Program demonstrates the implementation of Adjacency List.

Here is source code of the C++ Program to demonstrate the implementation of Adjacency List. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C++ Program to Implement Adjacency List

```
 */
```
```
#include <iostream>
```
```
#include <cstdlib>
```
```
using namespace std;
```
```
 
```
```
/*
```
```
 * Adjacency List Node
```
```
 */ 
```
```
struct AdjListNode
```
```
{
```
```
    int dest;
```
```
    struct AdjListNode* next;
```
```
};
```
```
 
```
```
/*
```
```
 * Adjacency List
```
```
 */  
```
```
struct AdjList
```
```
{
```
```
    struct AdjListNode *head;
```
```
};
```
```
 
```
```
/*
```
```
 * Class Graph
```
```
 */ 
```
```
class Graph
```
```
{
```
```
    private:
```
```
        int V;
```
```
        struct AdjList* array;
```
```
    public:
```
```
        Graph(int V)
```
```
        {
```
```
            this->V = V;
```
```
            array = new AdjList [V];
```
```
            for (int i = 0; i < V; ++i)
```
```
                array[i].head = NULL;
```
```
        }
```
```
        /*
```

         * Creating New Adjacency List Node

```
         */ 
```

        AdjListNode* newAdjListNode(int dest)

```
        {
```

            AdjListNode* newNode = new AdjListNode;

```
            newNode->dest = dest;
```
```
            newNode->next = NULL;
```
```
            return newNode;
```
```
        }
```
```
        /*
```
```
         * Adding Edge to Graph
```
```
         */ 
```
```
        void addEdge(int src, int dest)
```
```
        {
```

            AdjListNode* newNode = newAdjListNode(dest);

            newNode->next = array[src].head;

```
            array[src].head = newNode;
```

            newNode = newAdjListNode(src);

            newNode->next = array[dest].head;

```
            array[dest].head = newNode;
```
```
        }
```
```
        /*
```
```
         * Print the graph
```
```
         */ 
```
```
        void printGraph()
```
```
        {
```
```
            int v;
```
```
            for (v = 0; v < V; ++v)
```
```
            {
```

                AdjListNode* pCrawl = array[v].head;

                cout<<"\n Adjacency list of vertex "<<v<<"\n head ";

```
                while (pCrawl)
```
```
                {
```

                    cout<<"-> "<<pCrawl->dest;

                    pCrawl = pCrawl->next;

```
                }
```
```
                cout<<endl;
```
```
            }
```
```
        }
```
```
};
```
```
 
```
```
/*
```
```
 * Main
```
```
 */ 
```
```
int main()
```
```
{
```
```
    Graph gh(5);
```
```
    gh.addEdge(0, 1);
```
```
    gh.addEdge(0, 4);
```
```
    gh.addEdge(1, 2);
```
```
    gh.addEdge(1, 3);
```
```
    gh.addEdge(1, 4);
```
```
    gh.addEdge(2, 3);
```
```
    gh.addEdge(3, 4);
```
```
 
```

    // print the adjacency list representation of the above graph

```
    gh.printGraph();
```
```
 
```
```
    return 0;
```
```
}
```

$ g++ adjacency_list.cpp
$ a.out
 
 Adjacency list of vertex 0
 head -> 4-> 1
 
 Adjacency list of vertex 1
 head -> 4-> 3-> 2-> 0
 
 Adjacency list of vertex 2
 head -> 3-> 1
 
 Adjacency list of vertex 3
 head -> 4-> 2-> 1
 
 Adjacency list of vertex 4
 head -> 3-> 1-> 0
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - C++ Program to Implement Weak Heap

» Next - C++ Program to Implement Self Organising List

Related Posts:

Practice Design & Analysis of Algorithms MCQ
Check Programming Books
Check Data Structure Books
Apply for Computer Science Internship
Practice Programming MCQs

Recommended Articles: