#include <iostream>
#include <cstdlib>
usingnamespace std;
/*
* adjacency list node
*/
struct adjlistnode
{
int data;
struct adjlistnode* next;
};
/*
* adjacency list
*/
struct adjlist
{
struct adjlistnode *head;
};
/*
* class graph
*/
class graph
{
private:
int v;
adjlist* array;
public:
graph(int v)
{
this->v = v;
array = new adjlist[v]; //total vertices
for (int i = 0; i < v; ++i)
array[i].head = NULL; //linking head of all vertices (array) to null ,it doesn't store any number only stores head
}
/*
* adding edge to graph
*/
void addedge(int src, int dest)
{
// 0-->2
// 1-->null
// 2-->0
// add an edge from src to dest. a new node is added to the adjacency
// list of src. the node is added at the begining
adjlistnode* newnode = new adjlistnode; //newnode stores both data(dest) and *next pointer
newnode->data = dest; //consider src = 0 and dest = 1 0<----->1 for undirected graph
newnode->next = NULL; // 1----->null
//adding nodes at beginning of each list just like in linked list//
newnode->next = array[src].head; //*next(of dst) storing address of head->next node i.e.. 1--->2 (first node from head)
array[src].head = newnode; // 0-->1-->2
// since graph is undirected, add an edge from dest to src also
newnode = new adjlistnode; //now newnode storing data(src)
newnode->data = src;
newnode->next = NULL; // 0--->null
// newnode->next = array[dest].head; // 0---->null (bcuz.. 1-->null)
// array[dest].head = newnode; // 1---->0
}
/*
* print the graph
*/
void printgraph(int z)
{
for (int i= 0; i < z; ++i)
{
adjlistnode* tmp = array[v].head; //tmp has the address of (0,1..)vertex head
cout << "\n adjacency list of vertex " << v << "\n head ";
while (tmp)
{
cout << "-> " << tmp->data;
tmp = tmp->next;
}
cout << endl;
}
}
};
/*
* main
*/
int main()
{
int x,y,z;
cout << "Enter number of vertices" << endl;
cin >> z;
graph gh(z);
for (int i = 0; i < z; i++)
{
cout << "how much data for vertex " << i << " ?" << endl;
cin >> x;
for (int j = 0; j < x; j++)
{
cin >> y;
gh.addedge(i, y);
}
}
// print the adjacency list representation of the above graph
gh.printgraph(z);
system("pause");
}
