Skip to main content

Depth-First-Search and Breadth-First-Search Traversal of Graph | DFS and BFS of Graph | Representation of Graph using Adjacency List using Linked List

 Problem Statement:- Represent a given graph using an adjacency list to perform DFS and BFS. Use the map of the area around the college as the graph. Identify the prominent landmarks as nodes and perform DFS and BFS on that.

Note:- Scroll horizontally to see the full line of code.

#include <iostream>
#include <string.h>
using namespace std;

class flagarray
{
    string data;
    int flag;

public:
    flagarray()
    {
        this->data = "";
        this->flag = 0;
    }
    flagarray(string data, int flag)
    {
        this->data = data;
        this->flag = flag;
    }
    friend class stack;
    friend class queue;
    friend class node;
    friend class graph;
};

class stack;
class queue;

class stack
{
    int top = -1;
    string arr[30];

public:
    bool isFull();
    bool isEmpty();
    void push(string data);
    string Top();
    string pop();
};

void stack::push(string data)
{
    if (!isFull())
    {
        top++;
        arr[top] = data;
    }
    else
    {
        cout << "Stack is full!!! in push" << endl;
    }
}

string stack::Top()
{
    if (!isEmpty())
    {
        return arr[top];
    }
    else
    {
        cout << "Stack is Empty!!!" << endl;
        return "Empty";
    }
}

bool stack::isFull()
{
    return (top >= 29);
}

bool stack::isEmpty()
{
    return (top == -1);
}

string stack::pop()
{
    if (!isEmpty())
    {
        return arr[top--];
    }
    else
    {
        cout << "Stack is Empty!!!" << endl;
        return "Empty";
    }
}

class queue
{
    int front = -1, rear = -1;
    string arr[30];

public:
    bool isFull();
    bool isEmpty();
    void push(string data);
    string Front();
    string pop();
    string Rear();
};

bool queue::isFull()
{
    return (rear > 29);
}

bool queue::isEmpty()
{
    return (front > rear);
}

void queue::push(string data)
{
    if (!isFull())
    {
        if (front == -1)
        {
            front++;
        }
        arr[++rear] = data;
    }
    else
    {
        cout << "Queue is Full!!!" << endl;
    }
}

string queue::Front()
{
    if (!isEmpty())
    {
        return arr[front];
    }
    else
    {
        cout << "Queue is Empty" << endl;
        return "Empty";
    }
}

string queue::Rear()
{
    if (!isEmpty())
    {
        return arr[rear];
    }
    else
    {
        cout << "Queue is Empty" << endl;
        return "Empty";
    }
}

string queue::pop()
{
    if (!isEmpty())
    {
        return arr[front++];
    }
    else
    {
        cout << "Queue is Empty" << endl;
        return "Empty";
    }
}

class node
{
    string data;
    node *next;

public:
    node(string data)
    {
        this->data = data;
        next = NULL;
    }
    friend class graph;
    friend class stack;
    friend class queue;
};

class graph
{
    flagarray *BFS;
    flagarray *DFS;
    node **array;
    int vertexCount;

public:
    graph(int vertexCount)
    {
        this->vertexCount = vertexCount;
        array = new node *[vertexCount];
        BFS = new flagarray[vertexCount];
        DFS = new flagarray[vertexCount];
        for (int i = 0; i < vertexCount; i++)
        {
            array[i] = NULL;
        }
    }
    void createGraph();
    void display();
    int indexInBFS(string data);
    int indexInDFS(string data);
    int indexInArray(string data);
    void bfs();
    void dfs();
    friend class stack;
    friend class queue;
};

int graph::indexInBFS(string data)
{
    for (int i = 0; i < vertexCount; i++)
    {
        if (BFS[i].data == data)
        {
            return i;
        }
    }
    return -1;
}

int graph::indexInArray(string data)
{
    for (int i = 0; i < vertexCount; i++)
    {
        if (array[i]->data == data)
        {
            return i;
        }
    }
    return -1;
}
int graph::indexInDFS(string data)
{
    for (int i = 0; i < vertexCount; i++)
    {
        if (DFS[i].data == data)
        {
            return i;
        }
    }
    return -1;
}

void graph::createGraph()
{
    cout << "Enter the no. of Edges";
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cout << "Edge " << i + 1 << " : " << endl;
        string node1, node2;
        cout << "Enter node 1 of edge: ";
        cin >> node1;
        cout << "Enter node 2 of edge: ";
        cin >> node2;
        if (!array[0])
        {
            array[0] = new node(node1);
            array[1] = new node(node2);
            BFS[0].data = node1;
            DFS[0].data = node1;
            BFS[1].data = node2;
            DFS[1].data = node2;
            array[0]->next = new node(node2);
            array[1]->next = new node(node1);
        }
        else
        {
            int index1 = -1, index2 = -1;
            int index = 0;
            while (array[index] && index < vertexCount)
            {
                if (array[index]->data == node1)
                {
                    index1 = index;
                }
                if (array[index]->data == node2)
                {
                    index2 = index;
                }
                index++;
            }
            if (index1 == -1)
            {
                int j = 0;
                while (array[j])
                {
                    j++;
                }
                array[j] = new node(node1);
                BFS[i].data = node1;
                DFS[i].data = node1;
                array[j]->next = new node(node2);
            }
            else
            {
                node *current = array[index1];
                while (current->next)
                {
                    current = current->next;
                }
                current->next = new node(node2);
            }
            if (index2 == -1)
            {
                int j = 0;
                while (array[j])
                {
                    j++;
                }
                array[j] = new node(node2);
                BFS[j].data = node2;
                DFS[j].data = node2;
                array[j]->next = new node(node1);
            }
            else
            {
                node *current = array[index2];
                while (current->next)
                {
                    current = current->next;
                }
                current->next = new node(node1);
            }
        }
    }
}

void graph::display()
{
    if (array[0])
    {
        for (int i = 0; i < vertexCount; i++)
        {
            if (array[i])
            {
                node *current = array[i];
                cout << current->data;
                if (current->next)
                {
                    current = current->next;
                }
                while (current)
                {
                    cout << " --> " << current->data;
                    current = current->next;
                }
                cout << endl;
            }
        }
    }
    else
    {
        cout << "Graph is Empty!!!" << endl;
    }
}

void graph::dfs()
{
    stack dfsStack;
    node *current = array[0];
    dfsStack.push(current->data);
    DFS[indexInDFS(current->data)].flag = 1;
    while (!dfsStack.isEmpty())
    {
        string temp = dfsStack.pop();
        cout << temp << " ";
        current = array[indexInArray(temp)];
        while (current)
        {
            if (!DFS[indexInDFS(current->data)].flag)
            {
                dfsStack.push(current->data);
                DFS[indexInDFS(current->data)].flag = 1;
                current = current->next;
            }
            else
            {
                current = current->next;
            }
        }
    }
}
void graph::bfs()
{
    queue bfsQueue;
    node *current = array[0];
    bfsQueue.push(current->data);
    BFS[indexInBFS(current->data)].flag = 1;
    while (!bfsQueue.isEmpty())
    {
        string temp = bfsQueue.pop();
        cout << temp << " ";
        current = array[indexInArray(temp)];
        while (current)
        {
            if (!BFS[indexInBFS(current->data)].flag)
            {
                bfsQueue.push(current->data);
                BFS[indexInBFS(current->data)].flag = 1;
                current = current->next;
            }
            else
            {
                current = current->next;
            }
        }
    }
}

int main()
{
    int n;
    cout << "Enter the no. of Vertices: ";
    cin >> n;
    graph k(n);
    k.createGraph();
    char cont = 'y';
    while (cont == 'y')
    {
        cout << "<--------Menu-------->" << endl;
        cout << "1. Show Adjacency List" << endl;
        cout << "2. BFS Traversal" << endl;
        cout << "3. DFS Traversal" << endl;
        int choice;
        cout << "Enter the choice: ";
        cin >> choice;
        switch (choice)
        {
        case 1:
            cout << "Adjacency List for Graph : " << endl;
            k.display();
            break;

        case 2:
            cout << "BFS Traveral of Graph: ";
            k.bfs();
            cout << endl;
            break;

        case 3:
            cout << "DFS Traversal of Graph: ";
            k.dfs();
            cout << endl;
            break;

        default:
            cout << "Invalid Choice!!!" << endl;
            break;
        }
        cout << "Do you want to continue ? (y/n) : ";
        cin >> cont;
    }
    cout << "Program Ended Successfully!!!" << endl;
}

Labels:

Comments

Post a Comment

Popular posts from this blog

SET THEORY USING LIST IN PYTHON

Problem Statement :- In second-year computer engineering class, group A student's play cricket, group B students play badminton and group C students play football.  Write a Python program using functions to compute the following:-     a) List of students who play both cricket and badminton     b) List of students who play either cricket or badminton or both     c) Number of students who play neither cricket nor badminton     d) Number of students who play cricket and football but not badminton. (Note- While realizing the group, duplicate entries should be avoided, Do not use SET built-in functions) Note :- Scroll horizontally to see the full line of code. def   Addelem ( A ,  a ):      for   i   in   range  ( a ):          elem = input ( "Enter the name of student:" )          if ( elem   ...
Post a Comment
Read more

Uninstalling AnyDesk from Ubuntu: A Step-by-Step Guide

If you're an Ubuntu user looking to remove AnyDesk from your system and reclaim valuable space, this straightforward guide will walk you through the uninstallation process with easy-to-follow steps. Step 1: Launch the Terminal To initiate the uninstallation process, open the Terminal on your Ubuntu system by simultaneously pressing "Ctrl + Alt + T." Step 2: Verify AnyDesk Installation Confirm that AnyDesk is installed on your system by typing the following command in the Terminal and pressing "Enter": dpkg -l | grep anydesk The relevant information will be displayed if AnyDesk is installed. Step 3: Uninstall AnyDesk Remove AnyDesk from your Ubuntu system using the following command in the Terminal: sudo apt-get remove anydesk Enter your user password when prompted (characters won't be visible as you type) and press "Enter" to authorize the uninstallation. Step 4: Confirm Unins...
Post a Comment
Read more

Implementations of Search Algorithms using Python | Linear Sequential Search | Sentinel Sequential Search | Binary Search | Fibonacci Search

  Problem Statement:-  a) Write a Python program to store roll numbers of student in array who attended training program in random order. Write function for searching whether particular student attended training program or not, using Linear search and Sentinel search. b) Write a Python program to store roll numbers of students array who attended training program in sorted order. Write function for searching whether particular student attended training program or not, using Binary search and Fibonacci search. Note:-  Scroll horizontally to see the full line of code. def linear_search ( a , target ):     for i in range ( len ( a )):         if ( a [ i ]== target ):             print ( "Roll no." , target , "is present at index" , i )             break     else :         print ( "Roll no." , target , "not found in list" ) def binary_search ( a , targ...
Post a Comment
Read more

C++ Program for storing Appointments Schedule for day using Linked list | Display Free Slots | Book Appointment | Cancel Appointment | Sort Appointments

  Problem Statement: Write C++ program for storing appointment schedule for day. Appointments are booked randomly using linked list. Set start and end time and min and max duration for visit slot. Write Functions for-     A) Display free slots     B) Book appointments     C) Sort list based on time     D) Cancel appointment ( check validity, time bounds, availability )     E) Sort list base on time using pointer manipulation. Note: Scroll Horizontally to see the full line of code. #include < iostream > using namespace std ; class slot { public :     int startTime , endTime , min , max ;     bool status ;     slot * next ;     slot ( int start , int end , int min , int max )     {         startTime = start ;         endTime = end ;         this -> min = min ;         this ->...
Post a Comment
Read more

Complete Guide: Uninstalling Steam from Ubuntu - Step-by-Step

Steam is widely favored among gamers for its seamless game distribution and vibrant community engagement. However, excessive game installations can burden your PC, leading to sluggish performance and potential system crashes. If you're facing such issues, a thorough uninstallation of Steam from your Ubuntu system might be the solution. Simply removing Steam using standard methods may leave residual files and directories on your device, potentially causing lingering issues. This comprehensive guide will walk you through the process of completely removing Steam from your Ubuntu system. Steps to Fully Uninstall Steam from Ubuntu: Before proceeding, ensure to back up any important data as uninstalling Steam will also remove all associated games, DLCs, and saved data. Follow these steps to uninstall Steam from Ubuntu: Step 1: Open the terminal by right-clicking or pressing “ctrl...
Post a Comment
Read more