C++ Program to create Adjacency List of a Graph (Directedd or Undirected).

adjlist.cpp

/*
	Adjacency List of a graph
	- Ajinkya Sonawane [AJ-CODE-7]
*/

#include<iostream>
#include<queue>
#define INFINITY 9999	//Defining INFINITY to 9999
using namespace std;

class node
{
		int data;	//data field for a node
		int distance;	//distance field from a particular node
		node *next;	//link to the next node in adjacency list
		friend class graph;	//Allow class graph to access private members of class node
		public:
			node(){ distance = INFINITY;}	//initializing distance to INFINITY
};

class graph
{
	private:
		int **mat;	//decalring double pointer for a 2D array	
		int check;	//flag to check whether Direcred or Undirected
		int total,*v;	//array (v) for keeping track of visited nodes
		node **arr;	//Array of Pointer for Adjacency List
		queue<int> q;	//STL queue for BFS traversal
	public:
		graph();
		inline int get_flag() { return check; }	//Getter method for flag 
		void accept();		//Method to accept elements and creating a adjacency matrix
		void create_list();	//Method to create the adjacency list
		void display();		//Method to display Adjacency list
		void bfs();		//Method to print BFS traversal of the graph
		~graph();
};

graph :: graph()
{
	int ch;
	cout<<"\n\t\t|| Adjacency List ||\n";
	cout<<"\n\n1.Directed Graph";
	cout<<"\n2.Undirected Graph";
	cout<<"\n>>";
	cin>>ch;
	switch(ch)
	{
		case 1:
			check = 1;
			break;
		case 2:
			check = 0;
			break;
		default:
			check = 2;
			cout<<"\n\t********Invalid Choice*********\n";
			return;
	}
	
	//Accepting total number of cities
	cout<<"\nEnter the total number of cities : ";
	cin>>total;
	
	mat = new int*[total+1];
	v = new int[total+1];	//dynamically allocating memory for visited array
	arr = new node*[total+1];
	
	//dynamically allocating memory for adjacency matrix
	for(int i=1;i<=total;++i)
		mat[i]= new int[total];	
	
	
	for(int i=1;i<=total;i++)
	{
		v[i] = 0;
		arr[i] = new node;
		arr[i]->next = NULL;
		for(int j=1;j<=total;j++)
		{
			mat[i][j] = 0;	//Initializing all values of the adjacency matrix to 0
		}
	}
	
}

void graph :: accept()
{
	int a,b,dis;
	char ch;
	node *temp;
	//Displaying Names of cities as numeric values
	cout<<"\nNames of cities are : ";
	for(int i =1;i<=total;i++)
	{
		arr[i]->data = i;
		cout<<"\t"<<i;
	}
	cout<<endl;
	
	//Acceptin Connections between cities
	cout<<"\nEnter the connected cities as (1 2) : ";
	do
	{
	next:
		cout<<"\nEnter the cities : ";
		cin>>a>>b;
		if(a < 1 || b < 1 || a > total || b > total)
		{
			cout<<"\nInvalid City ,Enter again\n";
			goto next;
		}
		cout<<"\nEnter the distance in kms : ";
		cin>>dis;		
		
		//Storing Distance in adjacency matrix
		mat[a][b] = dis;	
		if(check == 0)
			mat[b][a] = dis;
		cout<<"\ny to add more .... n to exit : ";
		cin>>ch;
	}while(ch=='y');
	
	//Calling create_list method to create adjacency list
	create_list();
}

void graph :: create_list()
{
	node *cur,*temp;
	for(int i=1;i<=total;i++)
	{
		cur = arr[i];	//cur is node pointer to traverse the array of nodes
		for(int j=1;j<=total;j++)
		{
			if(mat[i][j] != 0)
			{
				temp = new node;	//temp is a node pointer to traverse each linked list
				temp->data = j;
				temp->distance = mat[i][j];
				cur->next = temp;
				temp->next = NULL;
				cur = temp;
			}			
		}
	}	
}

void graph :: bfs()
{
	//Method to display BFS traversal
	node* cur;
	for(int i=1;i<=total;i++)
	{
		cur = arr[i];
		while(cur != NULL)
		{
			if(!v[cur->data])
			{
				q.push(cur->data);	//pushing element in queue
				v[cur->data] = 1;	//setting visited node to 1
			}
			cur = cur->next;				
		}
	}	
	
	cout<<"\n|| BFS : ||\t";
	for(int i=0;i<total;i++)
	{
		int x = q.front();
		q.pop();
		cout<<x<<"\t";
	}
	cout<<endl;	
}

void graph :: display()
{
	node *cur;
	
	//display adjacency matrix
	cout<<"\n\t\t|| The Adjacency Matrix ||\n\n";
	for(int i=1;i<=total;i++)
	{
		for(int j=1;j<=total;j++)
		{
			cout<<mat[i][j]<<"\t";
		}
		cout<<endl;
	}
	
	//display adjacency list
	cout<<"\n\t\t|| Adjacency List ||\n";
	cout<<"\n\t\tCity , Distance in kms \n";
	for(int i=1;i<=total;i++)
	{
		cur = arr[i];	//Traversing array of nodes to print the linked list
		cout<<"\nAdjacent cities of ";
		while(true)
		{
			cout<<cur->data;
			if(cur->distance == INFINITY)
			{
				if(cur->next != NULL)
					cout<<"-->";	
			}
			else
			{
				if(cur->next != NULL)
					cout<<","<<cur->distance<<"kms-->";
				else
					cout<<","<<cur->distance<<"kms";
			}
			if(cur->next != NULL)
				cur = cur->next;
			else
				break;	
		}
	}	
	cout<<endl;	
}

graph :: ~graph()
{	
	delete arr;
	delete mat;
	delete v;
}
int main()
{
start:	//label to start if choice is not valid
	
	graph *g = new graph(); //allocating memory to object of class graph
	
	if(g->get_flag() == 2)
	{
		delete g;
		goto start;
	}
	//calling methods for performing the actions
	g->accept();	
	g->display();
	g->bfs();
	
	cout<<"\n\t\t*********Exit*******\n";
}

Proper creation of list and matrix Good work