Teacher name: Dr.

Musarrat Abdullah
Designation: Associate professor
Course: Data structures and Algorithms
Lab manual no:
Lab title: Graphs

ADJACENCY LIST
1. Introduction
Definition: In Data Structures and Algorithms (DSA), an adjacency list is a common way to represent a
graph. It's particularly useful for efficiently handling sparse graphs. The adjacency list consists of an array
(or a list) of lists. Each element of the main array represents a vertex, and each corresponding sub list
contains the neighbors (or adjacent vertices) of that vertex.

Analogy: Imagine you have a group of friends, and you want to keep track of who is friends with whom.
Each person is a node, and a friendship between two people is an edge.

1
2. Key Operations

 Adding an Edge:
To add an edge between two vertices u and v, you append v to the adjacency list of u and vice
versa (for undirected graphs).
-Time Complexity (O (1)) - This operation is constant time because appending to a list is a
constant-time operation.

 Removing an Edge:
To remove an edge between two vertices and v, you remove v from the adjacency list of u and
vice versa (for undirected graphs).
- Time Complexity: (O(V)) - In the worst case, you may need to search for v in the adjacency list
of u, which can take (O(V)) time, where V is the number of vertices.

 Adding a Vertex:
To add a vertex u, you simply create a new entry in the adjacency list with an empty list.
- Time Complexity: (O (1)) - This operation is constant time because it involves creating a new
entry in a data structure.

 Removing a Vertex:
To remove a vertex u, you delete its entry from the adjacency list and also remove u from the
adjacency lists of all other vertices.
- Time Complexity: (O (V + E)) - Removing a vertex involves deleting u from V adjacency lists
(which takes (O(V)) time) and searching and removing u from E edges (which also takes (O(E))
time).

 Checking if an Edge Exists:

To check if there is an edge between vertices u and v, you check if vis in the adjacency list of u.
- Time Complexity: (O(V)) - In the worst case, you may need to search for v in the adjacency list
of u, which takes (O(V)) time.

 Traversing the Graph:

To traverse the graph, you iterate through each vertex and then iterate through its adjacency list to
visit its neighbors.
- Time Complexity: (O (V + E)) - This is the sum of the number of vertices V and the number of
edges E. You visit each vertex once and each edge once.

 Finding Adjacent Vertices:

To find all vertices adjacent to a vertex u, you simply return its adjacency list.
- Time Complexity: (O (1)) - Accessing an element in an adjacency list is a constant-time
operation.

3. Implementation

An adjacency list can be implemented using arrays or linked lists.

In an array-based implementation, we use an array where each element is a list to store the adjacent
vertices of each vertex. The index of the array represents the vertex, and the list at each index contains its
adjacent vertices. To add an edge, we append the destination vertex to the list of the source vertex. For
undirected graphs, we add the source vertex to the list of the destination vertex as well. Removing an

2
edge involves removing the destination vertex from the source vertex's list and vice versa for undirected
graphs. This method is efficient for fixed-size graphs but can be less flexible for dynamic scenarios.

In a linked list-based implementation, we use a list where each element is a linked list to store the
adjacent vertices of each vertex. Each vertex is represented by a node, and each node points to another
linked list containing its adjacent vertices. To add an edge, we add a node for the destination vertex to the
source vertex's linked list, and for undirected graphs, we also add a node for the source vertex to the
destination vertex's linked list. Removing an edge requires traversing the linked list to find and remove
the node. This method offers more flexibility for dynamic graphs but can be slower due to the need for
traversal operations.

SAMPLE CODES

Implementation with Linked List

Write a program which takes input of an undirected or directed graph as an adjacency list and find
out whether there are any loops in the graph.

#include <iostream>
using namespace std;

void insert_node(char node_name);

void delete_node(char u);
void delnode_edge(char u);
void insert_edge(char u, char v);
void del_edge(char u, char v);
void display();
void successors(char u);
void predecessors(char u);

struct edge;
struct node {
char name;
node *next;
edge *adj;
} *start = NULL;

struct edge {
char dest;
edge *link;
};

node* find(char item);

int main() {
int choice;
char node, origin, destin;

while (1) {
cout << "1. Insert a node\n";

3
cout << "2. Insert an edge\n";
cout << "3. Delete a node\n";
cout << "4. Delete an edge\n";
cout << "5. Display\n";
cout << "6. Find successors\n";
cout << "7. Find predecessors\n";
cout << "8. Exit\n";
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "\nEnter a node to be inserted: ";
cin >> node;
insert_node(node);
break;
case 2:
cout << "\nEnter an edge's origin to be inserted: ";
cin >> origin;
cout << "\nEnter an edge's destination to be inserted: ";
cin >> destin;
insert_edge(origin, destin);
break;
case 3:
cout << "\nEnter a node to be deleted: ";
cin >> node;
delete_node(node); // This fn deletes the node from header node list.
delnode_edge(node); // This fn deletes all edges coming to this node.
break;
case 4:
cout << "\nEnter an edge's origin to be deleted: ";
cin >> origin;
cout << "\nEnter an edge's destination to be deleted: ";
cin >> destin;
del_edge(origin, destin);
break;
case 5:
display();
break;
case 6:
cout << "\nEnter the node to find successors: ";
cin >> node;
successors(node);
break;
case 7:
cout << "\nEnter the node to find predecessors: ";
cin >> node;
predecessors(node);
break;
case 8:
exit(1);

4
 break;
default:
cout << "\nWrong choice!\n";
break;
}
}

return 0;
}

void insert_node(char node_name) {

node *tmp, *ptr;
tmp = new node;
tmp->name = node_name;
tmp->next = NULL;
tmp->adj = NULL;

if (start == NULL) {
start = tmp;
return;
}

ptr = start;

while (ptr->next != NULL)

ptr = ptr->next;

ptr->next = tmp;
}

void delete_node(char u) {
node *tmp, *q;

if (start->name == u) {
tmp = start;
start = start->next; /* first element deleted */
delete tmp;
return;
}

q = start;

while (q->next->next != NULL) {

if (q->next->name == u) { /* element deleted in between */
tmp = q->next;
q->next = tmp->next;
delete tmp;
return;
}

q = q->next;

5
 }

if (q->next->name == u) { /* last element deleted */

tmp = q->next;
delete tmp;
q->next = NULL;
}
}

void delnode_edge(char u) {
node *ptr;
edge *q, *tmp;

ptr = start;

while (ptr != NULL) {

if (ptr->adj != NULL && ptr->adj->dest == u) {
tmp = ptr->adj;
ptr->adj = ptr->adj->link; /* first element deleted */
delete tmp;
continue; /* continue searching in another edge lists */
}

q = ptr->adj;

while (q != NULL && q->link != NULL) {

if (q->link->dest == u) { /* element deleted in between */
tmp = q->link;
q->link = tmp->link;
delete tmp;
continue;
}

q = q->link;
}

if (q != NULL && q->link != NULL && q->link->dest == u) { /* last element deleted */

tmp = q->link;
delete tmp;
q->link = NULL;
}

ptr = ptr->next;
}
}

void insert_edge(char u, char v) {

node *locu, *locv;
edge *ptr, *tmp;

locu = find(u);

6
 locv = find(v);

if (locu == NULL) {
cout << "\nSource node not present, first insert node " << u;
return;
}

if (locv == NULL) {
cout << "\nDestination node not present, first insert node " << v;
return;
}

tmp = new edge;

tmp->dest = v;
tmp->link = NULL;

if (locu->adj == NULL) { /* item added at the beginning */

locu->adj = tmp;
} else {
ptr = locu->adj;

while (ptr->link != NULL)

ptr = ptr->link;

ptr->link = tmp;
}
}

node* find(char item) {

node *ptr, *loc;
ptr = start;

while (ptr != NULL) {

if (item == ptr->name) {
loc = ptr;
return loc;
} else {
ptr = ptr->next;
}
}

loc = NULL;
return loc;
}

void del_edge(char u, char v) {

node *locu;
edge *ptr, *tmp, *q;

locu = find(u);

7
 if (locu == NULL) {
cout << "\nSource node not present\n";
return;
}

if (locu->adj != NULL && locu->adj->dest == v) {

tmp = locu->adj;
locu->adj = locu->adj->link; /* first element deleted */
delete tmp;
return;
}

q = locu->adj;

while (q != NULL && q->link != NULL) {

if (q->link->dest == v) { /* element deleted in between */
tmp = q->link;
q->link = tmp->link;
delete tmp;
return;
}

q = q->link;
}

if (q != NULL && q->link != NULL && q->link->dest == v) { /* last element deleted */

tmp = q->link;
delete tmp;
q->link = NULL;
return;
}

cout << "\nThis edge not present in the graph\n";

}

void display() {
node *ptr;
edge *q;

ptr = start;

while (ptr != NULL) {

cout << ptr->name << " -> ";
q = ptr->adj;

while (q != NULL) {
cout << q->dest << " ";
q = q->link;
}

cout << endl;

8
 ptr = ptr->next;
}
}

void successors(char u) {
node* loc = find(u);
bool hasoutdegree = false;
if(loc == NULL){
cout<<"Node not present in the graph"<<endl;
}
cout<<"Successors of the node "<<u<<" are : ";
edge* q = loc->adj;
while(q !=NULL){
cout<<q->dest<<" ";
hasoutdegree = true;
q = q->link;
}
if(!hasoutdegree){
cout<<"None";
}
cout<<endl;

void predecessors(char u) {
node *ptr;
edge *q;
ptr = start;
bool hasIndegree = false;
cout << "Predecessors of node " << u << " are: ";
while (ptr != NULL) {
q = ptr->adj;
while (q != NULL) {
if (q->dest == u) {
cout << ptr->name << " ";
hasIndegree = true;
}
q = q->link;
}
ptr = ptr->next;
}
if (!hasIndegree) {
cout << "None";
}
cout << endl;
}

9
Write a program to find the indegree and outdegree of a node in a directed graph using adjacency
list.

#include <iostream>
using namespace std;

void insert_node(char node_name);

void delete_node(char u);
void delnode_edge(char u);
void insert_edge(char u, char v);
void del_edge(char u, char v);
void display();
void indegree(char u);
void outdegree(char u);

struct edge;
struct node {
char name;
node *next;
edge *adj;
} *start = NULL;

struct edge {
char dest;
edge *link;
};

node* find(char item);

int main() {
int choice;
char node, origin, destin;

while (1) {
cout << "1. Insert a node\n";
cout << "2. Insert an edge\n";
cout << "3. Delete a node\n";
cout << "4. Delete an edge\n";
cout << "5. Display\n";
cout << "6. Display Indegrees of a node\n";
cout << "7. Display Outdegrees of a node\n";
cout << "8. Exit\n";

cout << "Enter your choice: ";

cin >> choice;

switch (choice) {
case 1:
cout << "\nEnter a node to be inserted: ";

10
 cin >> node;
insert_node(node);
break;
case 2:
cout << "\nEnter an edge's origin to be inserted: ";
cin >> origin;
cout << "\nEnter an edge's destination to be inserted: ";
cin >> destin;
insert_edge(origin, destin);
break;
case 3:
cout << "\nEnter a node to be deleted: ";
cin >> node;
delete_node(node); // This fn deletes the node from header node list.
delnode_edge(node); // This fn deletes all edges coming to this node.
break;
case 4:
cout << "\nEnter an edge's origin to be deleted: ";
cin >> origin;
cout << "\nEnter an edge's destination to be deleted: ";
cin >> destin;
del_edge(origin, destin);
break;
case 5:
display();
break;
case 6:
cout << "\nEnter a node : ";
cin >> node;
indegree(node);
break;
case 7:
cout << "\nEnter a node: ";
cin >> node;
outdegree(node);
break;
case 8:
exit(1);
break;
default:
cout << "\nWrong choice!\n";
break;
}
}

return 0;
}

void insert_node(char node_name) {

node *tmp, *ptr;
tmp = new node;

11
 tmp->name = node_name;
tmp->next = NULL;
tmp->adj = NULL;

if (start == NULL) {
start = tmp;
return;
}

ptr = start;

while (ptr->next != NULL)

ptr = ptr->next;

ptr->next = tmp;
}

void delete_node(char u) {
node *tmp, *q;

if (start->name == u) {
tmp = start;
start = start->next; /* first element deleted */
delete tmp;
return;
}

q = start;

while (q->next->next != NULL) {

if (q->next->name == u) { /* element deleted in between */
tmp = q->next;
q->next = tmp->next;
delete tmp;
return;
}

q = q->next;
}

if (q->next->name == u) { /* last element deleted */

tmp = q->next;
delete tmp;
q->next = NULL;
}
}

void delnode_edge(char u) {
node *ptr;
edge *q, *tmp;

12
 ptr = start;

while (ptr != NULL) {

if (ptr->adj != NULL && ptr->adj->dest == u) {
tmp = ptr->adj;
ptr->adj = ptr->adj->link; /* first element deleted */
delete tmp;
continue; /* continue searching in another edge lists */
}

q = ptr->adj;

while (q != NULL && q->link != NULL) {

if (q->link->dest == u) { /* element deleted in between */
tmp = q->link;
q->link = tmp->link;
delete tmp;
continue;
}

q = q->link;
}

if (q != NULL && q->link != NULL && q->link->dest == u) { /* last element deleted */

tmp = q->link;
delete tmp;
q->link = NULL;
}

ptr = ptr->next;
}
}

void insert_edge(char u, char v) {

node *locu, *locv;
edge *ptr, *tmp;

locu = find(u);
locv = find(v);

if (locu == NULL) {
cout << "\nSource node not present, first insert node " << u;
return;
}

if (locv == NULL) {
cout << "\nDestination node not present, first insert node " << v;
return;
}

tmp = new edge;

13
 tmp->dest = v;
tmp->link = NULL;

if (locu->adj == NULL) { /* item added at the beginning */

locu->adj = tmp;
} else {
ptr = locu->adj;

while (ptr->link != NULL)

ptr = ptr->link;

ptr->link = tmp;
}

node* find(char item) {

node *ptr, *loc;
ptr = start;

while (ptr != NULL) {

if (item == ptr->name) {
loc = ptr;
return loc;
} else {
ptr = ptr->next;
}
}

loc = NULL;
return loc;
}

void del_edge(char u, char v) {

node *locu;
edge *ptr, *tmp, *q;

locu = find(u);

if (locu == NULL) {
cout << "\nSource node not present\n";
return;
}

if (locu->adj != NULL && locu->adj->dest == v) {

tmp = locu->adj;
locu->adj = locu->adj->link; /* first element deleted */
delete tmp;
return;
}

14
 q = locu->adj;

while (q != NULL && q->link != NULL) {

if (q->link->dest == v) { /* element deleted in between */
tmp = q->link;
q->link = tmp->link;
delete tmp;
return;
}

q = q->link;
}

if (q != NULL && q->link != NULL && q->link->dest == v) { /* last element deleted */

tmp = q->link;
delete tmp;
q->link = NULL;
return;
}

cout << "\nThis edge not present in the graph\n";

}

void display() {
node *ptr;
edge *q;

ptr = start;

while (ptr != NULL) {

cout << ptr->name << " -> ";
q = ptr->adj;

while (q != NULL) {
cout << q->dest << " ";
q = q->link;
}

cout << endl;

ptr = ptr->next;
}
}

void indegree(char u ){
node *ptr;
edge *q;
ptr = start;
bool hasIndegree = false;
cout << "Nodes contributing to the indegree of node " << u << " are: ";
while (ptr != NULL) {

15
 q = ptr->adj;
while (q != NULL) {
if (q->dest == u) {
cout << ptr->name << " ";
hasIndegree = true;
}
q = q->link;
}
ptr = ptr->next;
}
if (!hasIndegree) {
cout << "None";
}
cout << endl;
}

void outdegree(char u){

node* loc = find(u);
bool hasoutdegree = false;
if(loc == NULL){
cout<<"Node not present in the graph"<<endl;
}
cout<<"Outdegree of the node "<<u<<" are : ";
edge* q = loc->adj;
while(q !=NULL){
cout<<q->dest<<" ,";
hasoutdegree = true;
q = q->link;
}
if(!hasoutdegree){
cout<<"None";
}
cout<<endl;

Implementation with Array

Write a program to find out the number of source nodes and sink nodes in an undirected graph
using adjacency list.

#include <iostream>
using namespace std;

const int MAX = 100;

int graph[MAX][MAX];
int nodes[MAX];
int node_count = 0;

16
void insert_node(int node_name);
void delete_node(int u);
void insert_edge(int u, int v);
void del_edge(int u, int v);
void display();
int indegree(int u);
int outdegree(int u);
void sourcesink();

int find(int item);

int main() {
int choice;
int node, origin, destin;

while (1) {
cout << "1. Insert a node\n";
cout << "2. Insert an edge\n";
cout << "3. Delete a node\n";
cout << "4. Delete an edge\n";
cout << "5. Display\n";
cout << "6. Display Indegrees of a node\n";
cout << "7. Display Outdegrees of a node\n";
cout << "8. Exit\n";
cout << "9. Check source and sink nodes\n";
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "\nEnter a node to be inserted: ";
cin >> node;
insert_node(node);
break;
case 2:
cout << "\nEnter an edge's origin to be inserted: ";
cin >> origin;
cout << "\nEnter an edge's destination to be inserted: ";
cin >> destin;
insert_edge(origin, destin);
break;
case 3:
cout << "\nEnter a node to be deleted: ";
cin >> node;
delete_node(node);
break;
case 4:
cout << "\nEnter an edge's origin to be deleted: ";
cin >> origin;
cout << "\nEnter an edge's destination to be deleted: ";

17
 cin >> destin;
del_edge(origin, destin);
break;
case 5:
display();
break;
case 6:
cout << "\nEnter a node: ";
cin >> node;
cout << "Indegree of node " << node << " is " << indegree(node) << endl;
break;
case 7:
cout << "\nEnter a node: ";
cin >> node;
cout << "Outdegree of node " << node << " is " << outdegree(node) << endl;
break;
case 8:
exit(1);
break;
case 9:
sourcesink();
break;
default:
cout << "\nWrong choice!\n";
break;
}
}

return 0;
}

void insert_node(int node_name) {

if (node_count < MAX) {
nodes[node_count++] = node_name;
} else {
cout << "Node limit reached" << endl;
}
}

void delete_node(int u) {
int index = find(u);
if (index == -1) {
cout << "Node not found" << endl;
return;
}

for (int i = 0; i < node_count; i++) {

graph[i][index] = 0;
graph[index][i] = 0;
}

18
 for (int i = index; i < node_count - 1; i++) {
nodes[i] = nodes[i + 1];
for (int j = 0; j < node_count; j++) {
graph[j][i] = graph[j][i + 1];
graph[i][j] = graph[i + 1][j];
}
}

node_count--;
}

void insert_edge(int u, int v) {

int origin = find(u);
int destin = find(v);

if (origin == -1 || destin == -1) {

cout << "One or both nodes not found" << endl;
return;
}

graph[origin][destin] = 1;
}

void del_edge(int u, int v) {

int origin = find(u);
int destin = find(v);

if (origin == -1 || destin == -1) {

cout << "One or both nodes not found" << endl;
return;
}

graph[origin][destin] = 0;
}

void display() {
for (int i = 0; i < node_count; i++) {
cout << nodes[i] << " -> ";
for (int j = 0; j < node_count; j++) {
if (graph[i][j]) {
cout << nodes[j] << " ";
}
}
cout << endl;
}
}

int find(int item) {

for (int i = 0; i < node_count; i++) {
if (nodes[i] == item) {
return i;

19
 }
}
return -1;
}

int indegree(int u) {
int index = find(u);
if (index == -1) {
return -1;
}

int count = 0;
for (int i = 0; i < node_count; i++) {
if (graph[i][index]) {
count++;
}
}

return count;
}

int outdegree(int u) {
int index = find(u);
if (index == -1) {
return -1;
}

int count = 0;
for (int i = 0; i < node_count; i++) {
if (graph[index][i]) {
count++;
}
}

return count;
}

void sourcesink() {
int source = 0;
int sink = 0;

for (int i = 0; i < node_count; i++) {

int in = indegree(nodes[i]);
int out = outdegree(nodes[i]);

if (in == 0 && out > 0) {

source++;
}

if (in > 0 && out == 0) {

sink++;

20
 }
}

cout << "The source nodes in this graph are " << source << endl;
cout << "The sink nodes in this graph are " << sink << endl;
}

ADJENCY MARTICE

1. Introduction

Definition: The Adjacency Matrix is a 2D array (matrix) where each cell on index (i,j) stores
information about the edge from vertex i to vertex j.

Analogy: Imagine you have a group of friends: Alice, Bob, Charlie, and Diana. You want to track their
friendships using an adjacency matrix:

 Alice is friends with Bob and Charlie.

 Bob is friends with Alice and Diana.
 Charlie is friends only with Alice.
 Diana is friends only with Bob.

Now, representing their friendships in an adjacency matrix:

Alice Bob Charlie Diana

Alice 0 1 1 0
Bob 1 0 0 1
Charlie 1 0 0 0
Diana 0 1 0 0

21
2. Key Operations

 Adding an Edge:
Set (A[u][v] = 1) for an unweighted graph, or (A[u][v] = w) for a weighted graph (where (w) is
the weight of the edge).

 Removing an Edge:
Set (A[u][v] = 0) for an unweighted graph, or (A[u][v] = infinity) for a weighted graph.

 Adding a Vertex:
Extend the adjacency matrix by one row and one column, initializing entries as needed.

 Removing a Vertex:
Delete the corresponding row and column from the adjacency matrix, shifting remaining vertices
as necessary.

 Traversing the Graph:

Iterate through each vertex and examine its row or column in the adjacency matrix to determine
adjacent vertices.

 Finding Adjacent Vertices:

Iterate through the row or column (A[u]) in the adjacency matrix.

3. Implementation

It is very easy and simple to implement an adjacency matrix for a graph there are certain steps given
below that you need to follow:

 Create an n x n matrix where n is the number of vertices in the graph.

 Initialize all elements to 0.
 For each edge (u, v) in the graph, if the graph is undirected mark a[u][v] and a[v][u] as 1, and if
the edge is directed from u to v, mark a[u][v] as the 1. (Cells are filled with edge weight if the
graph is weighted)

An adjacency matrix can be implemented using arrays or linked lists.

SAMPLE CODES

Write a function to check if there exists an edge between two vertices u and v in the adjacency
matrix.
#include <iostream>
using namespace std;

const int MAX_VERTICES = 100;

int adjMatrix[MAX_VERTICES][MAX_VERTICES];
int V;

22
bool isEdge(int u, int v) {
if (u < 0 || u >= V || v < 0 || v >= V)
return false;
return (adjMatrix[u][v] != 0);
}

void addEdge(int u, int v) {

if (u >= 0 && u < V && v >= 0 && v < V) {
adjMatrix[u][v] = 1; // For directed edge from u to v
adjMatrix[v][u] = 1; // For undirected edge (if needed)
}
}

void deleteEdge(int u, int v) {

if (u >= 0 && u < V && v >= 0 && v < V) {
adjMatrix[u][v] = 0;
adjMatrix[v][u] = 0; // For undirected graph
}
}

void displayMatrix() {
cout << "Adjacency Matrix:" << endl;
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
cout << adjMatrix[i][j] << " ";
}
cout << endl;
}
}

int main() {
V = 4;
addEdge(0, 1);
addEdge(1, 2);
addEdge(2, 3);
addEdge(3, 0);

displayMatrix();

deleteEdge(1, 2);
deleteEdge(3, 0);

cout << endl;

displayMatrix();

cout << endl;

cout << "Edge between 0 and 1: " << (isEdge(0, 1) ? "Yes" : "No") << endl;
cout << "Edge between 1 and 3: " << (isEdge(1, 3) ? "Yes" : "No") << endl;

return 0;
}

23
Write a function to detect if a directed graph represented by an adjacency matrix has any
cycles.

#include <iostream>
using namespace std;

#define MAX 20

int adj[MAX][MAX];
bool visited[MAX];
bool recursion_stack[MAX];
int n; // denotes number of nodes in the graph

bool dfs(int v) {
if (!visited[v]) {
visited[v] = true;
recursion_stack[v] = true;

for (int i = 1; i <= n; ++i) {

if (adj[v][i]) {
if (!visited[i] && dfs(i))
return true;
else if (recursion_stack[i])
return true;
}
}
}
recursion_stack[v] = false;
return false;
}

bool hasCycle() {
for (int i = 1; i <= n; ++i) {
visited[i] = false;
recursion_stack[i] = false;
}

for (int i = 1; i <= n; ++i) {

if (!visited[i]) {
if (dfs(i))
return true;
}
}
return false;
}
24
int main() {
int max_edges, origin, destin;

cout << "\nEnter number of nodes: ";

cin >> n;

max_edges = n * (n - 1);

cout << "\nEnter adjacency matrix:\n";

for (int i = 1; i <= max_edges; ++i) {
cout << "\nEnter edge origin " << i << " (00 to quit): ";
cin >> origin;
if (origin == 0)
break;
cout << "\nEnter edge destination " << i << " (00 to quit): ";
cin >> destin;
if (destin == 0)
break;

if (origin > n || destin > n || origin <= 0 || destin <= 0) {

cout << "\nInvalid edge!\n";
i--;
} else {
adj[origin][destin] = 1;
}
}

if (hasCycle())
cout << "\nThe graph has cycles.\n";
else
cout << "\nThe graph does not have cycles.\n";

return 0;
}

Write a program to calculate and print the transitive closure of a directed graph using its
adjacency matrix.

#include <iostream>
using namespace std;

#define MAX 20

int adj[MAX][MAX];

25
int transitive_closure[MAX][MAX];
int n; // number of nodes in the graph

void calculate_transitive_closure() {
// Initialize transitive closure with the adjacency matrix
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
transitive_closure[i][j] = adj[i][j];
}
}

// Use Floyd-Warshall algorithm to update transitive closure

for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (transitive_closure[i][k] && transitive_closure[k][j]) {
transitive_closure[i][j] = 1;
}
}
}
}
}

void display_transitive_closure() {
cout << "\nTransitive Closure:\n";
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cout << transitive_closure[i][j] << " ";
}
cout << endl;
}
}

int main() {
int max_edges, origin, destin;

cout << "\nEnter number of nodes: ";

cin >> n;

max_edges = n * (n - 1);

cout << "\nEnter adjacency matrix:\n";

for (int i = 1; i <= max_edges; ++i) {
cout << "\nEnter edge origin " << i << " (00 to quit): ";
cin >> origin;
if (origin == 0)

26
 break;
cout << "\nEnter edge destination " << i << " (00 to quit): ";
cin >> destin;
if (destin == 0)
break;

if (origin > n || destin > n || origin <= 0 || destin <= 0) {

cout << "\nInvalid edge!\n";
i--;
} else {
adj[origin][destin] = 1;
}
}

// Calculate transitive closure

calculate_transitive_closure();

// Display transitive closure

display_transitive_closure();

return 0;
}

GRAPHS TRAVERSAL

1. Introduction

Definition: To traverse a Graph means to start in one vertex, and go along the edges to visit other
vertices until all vertices, or as many as possible, have been visited.

27
The two most common ways a Graph can be traversed are:

 Depth First Search (DFS):

Depth-first search is an algorithm for traversing or searching tree or graph data structures. The
algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a
graph) and explores as far as possible along each branch before backtracking.

 Breadth First Search (BFS):

Breadth First Search (BFS) is a fundamental graph traversal algorithm. It involves visiting all the
connected nodes of a graph in a level-by-level manner.

Analogy:

 Depth-First Search (DFS) Analogy:

Imagine you're exploring a maze, starting at a specific point. In DFS, you follow a path as far as
you can before backtracking. It's like entering a corridor (edge) and exploring it fully (going
deep) before considering other corridors branching off from the same point. This method ensures
thorough exploration of one path before moving on to explore others.

28
  Breadth-First Search (BFS) Analogy:

Contrastingly, BFS explores the maze level by level. You start at the entrance (vertex) and explore
all adjacent corridors (edges) before moving on to corridors further away. It's akin to exploring all
possible paths of a certain length before moving to longer paths, ensuring you cover all
possibilities at the current depth level before progressing.

2. Key Operations

Graph traversal algorithms, such as Breadth-First Search (BFS) and Depth-First Search (DFS), perform
several key operations to explore and analyze graphs. Here are the key operations involved in graph
traversal:

 Visit a Vertex:
During traversal, each vertex is visited exactly once. Visiting a vertex involves marking it as
visited or processing it based on the traversal algorithm's requirements.

 Explore Neighbors (Edges):

Traversal algorithms examine each vertex's neighbors, which are connected by edges. For each
vertex, all adjacent vertices (neighbors) are considered in a specific order determined by the
traversal strategy.

 Marking Visited Vertices:

To avoid processing a vertex more than once and to prevent infinite loops in cyclic graphs,
traversal algorithms often mark vertices as visited once they are processed or added to the
traversal queue/stack.

 Maintain Traversal Order:

Traversal algorithms maintain a specific order in which vertices are processed. BFS processes
vertices in increasing order of their distance from the starting vertex (level-wise), while DFS
explores vertices depth-wise.

 Pathfinding and Shortest Paths:

29
 Traversal algorithms can be used to find paths between two vertices or determine the shortest path
from a starting vertex to all other vertices in unweighted graphs. BFS is particularly suitable for
finding the shortest path in unweighted graphs due to its level-wise exploration.

 Identify Connected Components:

Traversal algorithms can identify and enumerate connected components within a graph, helping
to understand the graph's structure and connectivity.

 Cycle Detection:
In directed and undirected graphs, traversal algorithms can detect cycles by observing revisited
vertices or back edges during traversal.

 Graph Representation and Visualization:

Traversal aids in visually representing and understanding the graph's structure. By traversing the
graph, you can generate and visualize its adjacency matrix, adjacency list, or other representations

3. Implementation
DFS Using a Stack

Depth-First Search (DFS) is a graph traversal method that explores as far down a branch as possible
before backtracking. It can be implemented using a stack, which helps in keeping track of the nodes to
visit next.

1. Initialization:
o Start with a stack containing the initial node.
o Use a set to keep track of visited nodes to avoid processing the same node multiple times.

2. Traversal Process:
o Pop a node from the stack.
o If the node has not been visited, mark it as visited and process it (e.g., print it or add it to
a result list).
o Push all unvisited adjacent nodes of the current node onto the stack.

3. Termination:
o The traversal continues until the stack is empty, meaning all reachable nodes have been
processed.

BFS Using a Queue

Breadth-First Search (BFS) is a graph traversal method that explores all neighbor nodes at the present
depth level before moving on to nodes at the next depth level. It can be implemented using a queue,
which helps in processing nodes in a first-in-first-out (FIFO) manner.

1. Initialization:
o Start with a queue containing the initial node.
o Use a set to keep track of visited nodes to avoid processing the same node multiple times.

2. Traversal Process:

30
 o Dequeue a node from the queue.
o If the node has not been visited, mark it as visited and process it (e.g., print it or add it to
a result list).
o Enqueue all unvisited adjacent nodes of the current node.

3. Termination:
o The traversal continues until the queue is empty, meaning all reachable nodes have been
processed

SAMPLE CODES

DFS Implementation
Write the program of DFS traversal of a directed graph using adjacency matrix for graph
representation and linked list representation for the traversal code. Provide its iterative and
recursive code.

#include <iostream>
using namespace std;

#define MAX 20

void create_graph();
void display();
void dfs_rec(int v);
void dfs(int v);
void bfs(int v);
void adj_nodes(int v);
void components();

int adj[MAX][MAX];
bool visited[MAX];
int n; // denotes number of nodes in the graph

int main() {
int i, v, choice;

create_graph();
while (1)
{
cout << "\n1.Adjacency matrix\n";
cout << "2.Depth First Search using stack\n";
cout << "3.Depth First Search through recursion\n";
cout << "4.Adjacent vertices\n";
cout << "5.Components\n";
cout << "6.Exit\n";
cout << "\nEnter your choice: ";
cin >> choice;

31
 switch (choice)
{
case 1:
cout << "\nAdjacency Matric\n";
display();
break;
case 2:
cout << "\nEnter starting node Depth First Search: ";
cin >> v;
for (i = 1; i <= n; i++)
visited[i] = false;
dfs(v);
break;
case 3:
cout << "\nEnter starting node for Depth First Search: ";
cin >> v;
for(i = 1; i <= n; i++)
visited[i] = false;
dfs_rec(v);
break;
case 4:
cout << "\nEnter node to find adjacent vertices: ";
cin >> v;
cout << "\nAdjacent Vertices are: ";
adj_nodes(v);
break;
case 5:
components();
break;
case 6:
exit(1);
default:
cout << "\nWrong choice\n";
break;

}
}
}

void create_graph() {
int i, max_edges, origin, destin;

cout << "\nEnter number of nodes: ";

cin >> n;

max_edges = n * (n-1);

for(i = 1; i <= max_edges; i++) {

cout << "\nEnter edge origin " << i << " (00 to quit): ";
cin >> origin;
cout << "\nEnter edge destination " << i << " (00 to quit): ";

32
 cin >> destin;

if((origin = 0) && (destin == 0))

break;

if(origin > n || destin > n || origin <= 0 || destin <= 0) {

cout << "\nInvalid edge!\n";
i--;
}

else {
adj[origin][destin] = 1;
}
}
}

void display() {
int i, j;

for(i = 1; i <= n; i++) {

for(j = 1; j <= n; j++)

cout << adj[i][j] << " ";
cout << endl;
}
}

void dfs_rec(int v) {
int i;
visited[v] = true;
cout << v;

for(i = 1; i <= n; i++) {

if(adj[v][i] == 1 && visited[i] == false)
dfs_rec(i);
}
}

void dfs(int v) {
int i, stack[MAX], top = -1, pop_v, j, t;
int ch;

top++;
stack[top] = v;

while (top >= 0) {

pop_v = stack[top];
top--; // pop from stack

if(visited[pop_v] == false) {
cout << pop_v << " ";

33
 visited[pop_v] = true;
}

else
continue;

for(i = n; i >= 1; i--) {

if(adj[pop_v][i] == 1 && visited[i] == false) {

top++; /* push all unvisited neighbours of pop_v */
stack[top] = i;
}
}
}
}

void adj_nodes(int v) {
int i;

for(i = 1; i <= n; i++) {

if(adj[v][i] == 1)
cout << i << " ";
cout << endl;
}
}

void components() {
int i;

for(i = 1; i <= n; i++)

visited[i] = false;

for(i = 1; i <= n; i++) {

if(visited[i] == false)
dfs_rec(i);
}

cout << endl;

Write a function to count the number of connected components in an undirected graph using DFS.
The graph is represented using an adjacency matrix.
#include <iostream>
using namespace std;

34
#define MAX 20

void create_graph();
void display();
void dfs_rec(int v);
void dfs(int v);
void bfs(int v);
void adj_nodes(int v);
void components();
int count_components();

int adj[MAX][MAX];
bool visited[MAX];
int n; // denotes number of nodes in the graph

int main() {
int i, v, choice;

create_graph();
while (1) {
cout << "\n1. Adjacency matrix\n";
cout << "2. Depth First Search using stack\n";
cout << "3. Depth First Search through recursion\n";
cout << "4. Adjacent vertices\n";
cout << "5. Components\n";
cout << "6. Count Connected Components\n";
cout << "7. Exit\n";
cout << "\nEnter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "\nAdjacency Matrix\n";
display();
break;
case 2:
cout << "\nEnter starting node for Depth First Search: ";
cin >> v;
for (i = 1; i <= n; i++)
visited[i] = false;
dfs(v);
cout << endl;
break;
case 3:
cout << "\nEnter starting node for Depth First Search: ";
cin >> v;
for (i = 1; i <= n; i++)
visited[i] = false;
dfs_rec(v);
cout << endl;
break;

35
 case 4:
cout << "\nEnter node to find adjacent vertices: ";
cin >> v;
cout << "\nAdjacent Vertices are: ";
adj_nodes(v);
cout << endl;
break;
case 5:
components();
break;
case 6:
cout << "Number of connected components: " << count_components() << endl;
break;
case 7:
exit(1);
default:
cout << "\nWrong choice\n";
break;
}
}
}

void create_graph() {
int i, max_edges, origin, destin;

cout << "\nEnter number of nodes: ";

cin >> n;

max_edges = n * (n - 1);

for (i = 1; i <= max_edges; i++) {

cout << "\nEnter edge origin " << i << " (00 to quit): ";
cin >> origin;
if (origin == 0)
break;
cout << "Enter edge destination " << i << " (00 to quit): ";
cin >> destin;
if (destin == 0)
break;

if (origin > n || destin > n || origin <= 0 || destin <= 0) {

cout << "\nInvalid edge!\n";
i--;
} else {
adj[origin][destin] = 1;
adj[destin][origin] = 1; // For undirected graph
}
}
}

void display() {

36
 int i, j;

for (i = 1; i <= n; i++) {

for (j = 1; j <= n; j++)
cout << adj[i][j] << " ";
cout << endl;
}
}

void dfs_rec(int v) {
int i;
visited[v] = true;
cout << v << " ";

for (i = 1; i <= n; i++) {

if (adj[v][i] == 1 && !visited[i])
dfs_rec(i);
}
}

void dfs(int v) {
int i, stack[MAX], top = -1, pop_v;

top++;
stack[top] = v;

while (top >= 0) {

pop_v = stack[top];
top--; // pop from stack

if (!visited[pop_v]) {
cout << pop_v << " ";
visited[pop_v] = true;
} else {
continue;
}

for (i = n; i >= 1; i--) {

if (adj[pop_v][i] == 1 && !visited[i]) {
top++; // push all unvisited neighbors of pop_v
stack[top] = i;
}
}
}
}

void adj_nodes(int v) {
int i;

for (i = 1; i <= n; i++) {

if (adj[v][i] == 1)

37
 cout << i << " ";
}
cout << endl;
}

void components() {
int i;

for (i = 1; i <= n; i++)

visited[i] = false;

for (i = 1; i <= n; i++) {

if (!visited[i]) {
dfs_rec(i);
cout << endl;
}
}
}

int count_components() {
int i, count = 0;

for (i = 1; i <= n; i++)

visited[i] = false;

for (i = 1; i <= n; i++) {

if (!visited[i]) {
dfs_rec(i);
count++;
}
}
return count;
}

BFS Implementation
Write the program of BFS traversal of a directed graph using adjacency matrix for graph
representation and linked list representation for the traversal code.

#include <iostream>
using namespace std;

#define MAX 20

void create_graph();
void display();
void dfs_rec(int v);

38
void dfs(int v);
void bfs(int v);
void adj_nodes(int v);
void components();

int adj[MAX][MAX];
bool visited[MAX];
int n; // denotes number of nodes in the graph

int main() {
int i, v, choice;

create_graph();
while (1)
{
cout << "\n1.Adjacency matrix\n";
cout << "2.Depth First Search using stack\n";
cout << "3.Depth First Search through recursion\n";
cout << "4.Breadth First Search\n";
cout << "5.Adjacent vertices\n";
cout << "6.Components\n";
cout << "7.Exit\n";
cout << "\nEnter your choice: ";
cin >> choice;

switch (choice)
{
case 1:
cout << "\nAdjacency Matric\n";
display();
break;
case 2:
cout << "\nEnter starting node Depth First Search: ";
cin >> v;
for (i = 1; i <= n; i++)
visited[i] = false;
dfs(v);
break;
case 3:
cout << "\nEnter starting node for Depth First Search: ";
cin >> v;
for(i = 1; i <= n; i++)
visited[i] = false;
dfs_rec(v);
break;
case 4:
cout << "\nEnter starting node for Breadth First Search: ";
cin >> v;
for(i = 1; i <= n; i++)
visited[i] = false;
bfs(v);

39
 break;
case 5:
cout << "\nEnter node to find adjacent vertices: ";
cin >> v;
cout << "\nAdjacent Vertices are: ";
adj_nodes(v);
break;
case 6:
components();
break;
case 7:
exit(1);
default:
cout << "\nWrong choice\n";
break;

}
}
}

void create_graph() {
int i, max_edges, origin, destin;

cout << "\nEnter number of nodes: ";

cin >> n;

max_edges = n * (n-1);

for(i = 1; i <= max_edges; i++) {

cout << "\nEnter edge origin " << i << " (00 to quit): ";
cin >> origin;
cout << "\nEnter edge destination " << i << " (00 to quit): ";
cin >> destin;

if((origin = 0) && (destin == 0))

break;

if(origin > n || destin > n || origin <= 0 || destin <= 0) {

cout << "\nInvalid edge!\n";
i--;
}

else {
adj[origin][destin] = 1;
}
}
}

void display() {
int i, j;

40
 for(i = 1; i <= n; i++) {

for(j = 1; j <= n; j++)

cout << adj[i][j] << " ";
cout << endl;
}
}

void dfs_rec(int v) {
int i;
visited[v] = true;
cout << v;

for(i = 1; i <= n; i++) {

if(adj[v][i] == 1 && visited[i] == false)
dfs_rec(i);
}
}

void dfs(int v) {
int i, stack[MAX], top = -1, pop_v, j, t;
int ch;

top++;
stack[top] = v;

while (top >= 0) {

pop_v = stack[top];
top--; // pop from stack

if(visited[pop_v] == false) {
cout << pop_v << " ";
visited[pop_v] = true;
}

else
continue;

for(i = n; i >= 1; i--) {

if(adj[pop_v][i] == 1 && visited[i] == false) {

top++; /* push all unvisited neighbours of pop_v */
stack[top] = i;
}
}
}
}

void bfs(int v) {
int i, front, rear;
int que[20];

41
 front = rear = -1;

cout << v;

visited[v] = true;
rear++;
front++;

que[rear] = v;

while (front <= rear) {

v = que[front]; /* delete from queue */
front++;

for(i = 1; i <= n; i++) {

/* Check for adjacent unvisited nodes */

if(adj[v][i] == 1 && visited[i] == false) {
cout << i << " ";
visited[i] = true;
rear++;
que[rear] = i;
}
}
}
}

void adj_nodes(int v) {
int i;

for(i = 1; i <= n; i++) {

if(adj[v][i] == 1)
cout << i << " ";
cout << endl;
}
}

void components() {
int i;

for(i = 1; i <= n; i++)

visited[i] = false;

for(i = 1; i <= n; i++) {

if(visited[i] == false)
dfs_rec(i);
}

cout << endl;

42
}

Write a C++ program to find if there is a path between two vertices in a directed graph
using BFS algorithm.

#include <iostream>
using namespace std;

#define MAX 20

void create_graph();
void display();
void dfs_rec(int v);
void dfs(int v);
void bfs(int v);
void adj_nodes(int v);
void components();
bool is_path_bfs(int start, int end);

int adj[MAX][MAX];
bool visited[MAX];
int n; // denotes number of nodes in the graph

int main() {
int i, v, choice;

create_graph();
while (1) {
cout << "\n1. Adjacency matrix\n";
cout << "2. Breadth First Search\n";
cout << "3. Adjacent vertices\n";
cout << "4. Components\n";
cout << "5. Find path between two vertices\n";
cout << "6. Exit\n";
cout << "\nEnter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "\nAdjacency Matrix\n";
display();
break;
case 2:
cout << "\nEnter starting node for Breadth First Search: ";
cin >> v;
for (i = 1; i <= n; i++)

43
 visited[i] = false;
bfs(v);
break;
case 3:
cout << "\nEnter node to find adjacent vertices: ";
cin >> v;
cout << "\nAdjacent Vertices are: ";
adj_nodes(v);
break;
case 4:
components();
break;
case 5: {
int start, end;
cout << "\nEnter start node: ";
cin >> start;
cout << "Enter end node: ";
cin >> end;
if (is_path_bfs(start, end))
cout << "\nThere is a path from " << start << " to " << end << "\n";
else
cout << "\nNo path exists from " << start << " to " << end << "\n";
break;
}
case 6:
exit(1);
default:
cout << "\nWrong choice\n";
break;
}
}
}

void create_graph() {
int i, max_edges, origin, destin;

cout << "\nEnter number of nodes: ";

cin >> n;

max_edges = n * (n - 1);

for (i = 1; i <= max_edges; i++) {

cout << "\nEnter edge origin " << i << " (00 to quit): ";
cin >> origin;
cout << "\nEnter edge destination " << i << " (00 to quit): ";
cin >> destin;

if (origin == 0 && destin == 0)

break;

if (origin > n || destin > n || origin <= 0 || destin <= 0) {

44
 cout << "\nInvalid edge!\n";
i--;
} else {
adj[origin][destin] = 1;
}
}
}

void display() {
int i, j;

for (i = 1; i <= n; i++) {

for (j = 1; j <= n; j++)
cout << adj[i][j] << " ";
cout << endl;
}
}

void bfs(int v) {
int i, front, rear;
int que[MAX];
front = rear = -1;

cout << v << " ";

visited[v] = true;
rear++;
front++;
que[rear] = v;

while (front <= rear) {

v = que[front]; /* delete from queue */
front++;

for (i = 1; i <= n; i++) {

/* Check for adjacent unvisited nodes */
if (adj[v][i] == 1 && !visited[i]) {
cout << i << " ";
visited[i] = true;
rear++;
que[rear] = i;
}
}
}
cout << endl;
}

void adj_nodes(int v) {
int i;

for (i = 1; i <= n; i++) {

45
 if (adj[v][i] == 1)
cout << i << " ";
}
cout << endl;
}

void components() {
int i;

for (i = 1; i <= n; i++)

visited[i] = false;

for (i = 1; i <= n; i++) {

if (!visited[i])
dfs_rec(i);
}

cout << endl;

}

void dfs_rec(int v) {
int i;
visited[v] = true;
cout << v << " ";

for (i = 1; i <= n; i++) {

if (adj[v][i] == 1 && !visited[i])
dfs_rec(i);
}
}

void dfs(int v) {
int i;
visited[v] = true;
cout << v << " ";

for (i = 1; i <= n; i++) {

if (adj[v][i] == 1 && !visited[i])
dfs(i);
}
}

bool is_path_bfs(int start, int end) {

if (start == end) return true;

int i, front, rear;

int que[MAX];
front = rear = -1;

for (i = 1; i <= n; i++)

visited[i] = false;

46
 visited[start] = true;
rear++;
front++;
que[rear] = start;

while (front <= rear) {

int v = que[front]; /* delete from queue */
front++;

for (i = 1; i <= n; i++) {

/* Check for adjacent unvisited nodes */
if (adj[v][i] == 1 && !visited[i]) {
if (i == end) return true;
visited[i] = true;
rear++;
que[rear] = i;
}
}
}

return false;
}

47