bfsANDfs.cpp

#include <iostream>
using namespace std;

const int MAX_NODES = 20;
int GRAPH[MAX_NODES][MAX_NODES];
bool visited[MAX_NODES] = {false};
int queue[MAX_NODES];
int stack[MAX_NODES];

void initialize(int node) {
  for (int i = 0; i < node; ++i) {
    cout << i << " ";
    for (int j = 0; j < node; ++j) GRAPH[i][j] = 0;
  }
  cout << "\n";
}
void addEdge(int source, int dest, int node, int &iterationNo) {
  if (source < 0 || source >= node || dest < 0 || dest >= node) {
    cout << "Please enter a valid number of source and destination: " << endl;
    iterationNo--;
    return;
  }
  if (GRAPH[source][dest] == 1) {
    cout << "Already present edge: " << endl;
    iterationNo--;
    return;
  }
  GRAPH[source][dest] = 1;
  GRAPH[dest][source] = 1;
}

void BFS(int start, int nodes) {
  if (start < 0 || start >= nodes) {
    cout << "Error: Starting node " << start << " does not exist.\n";
    return;
  }

  int front = 0, rear = 0;
  queue[rear] = start;
  rear++;
  visited[start] = true;

  cout << "BFS Traversal: ";
  while (front < rear) {
    int node = queue[front];
    front++;
    cout << node << " ";

    for (int i = 0; i < nodes; i++) {
      if (GRAPH[node][i] == 1 && !visited[i]) {
        queue[rear] = i;
        rear++;
        visited[i] = true;
      }
    }
  }
  cout << endl;
}

void DFS(int start, int nodes) {
  if (start < 0 || start >= nodes) {
    cout << "Error: Starting node " << start << " does not exist.\n";
    return;
  }

  int top = -1;
  top++;
  stack[top] = start;
  visited[start] = true;

  cout << "DFS Traversal: ";
  while (top >= 0) {
    int node = stack[top];
    top--;
    cout << node << " ";

    for (int i = 0; i < nodes; i++) {
      if (GRAPH[node][i] == 1 && !visited[i]) {
        top++;
        stack[top] = i;
        visited[i] = true;
      }
    }
  }
  cout << endl;
}

void mainMenu() {
  cout << "\n========================Menu========================\n";
  cout << "1. DFS Traversal\n";
  cout << "2. BFS Traversal\n";
  cout << "3. Exit\n";
  cout << "Enter your choice: ";
}

void resetVisited(int nodes) {
  for (int i = 0; i < nodes; i++) {
    visited[i] = false;
  }
}

int main() {
  int nodes, edges, choice, start;

  cout << "Enter the number of nodes: ";
  cin >> nodes;

  if (nodes <= 0 || nodes > MAX_NODES) {
    cout << "Error: Number of nodes must be between 1 and " << MAX_NODES
         << ".\n";
    return 1;
  }

  int max_edges =
      (nodes * (nodes - 1)) /
      2;  // Maximum edges for an undirected graph without self-loops
  cout << "Enter the number of edges: ";
  cin >> edges;

  while (edges < 0 || edges > max_edges) {
    cout << "Error: Number of edges must be between 0 and " << max_edges
         << ".\n";
    cout << "Enter the number of edges: ";
    cin >> edges;
  }

  initialize(nodes);

  cout << "Enter edges (source destination):\n";
  for (int i = 0; i < edges; i++) {
    int source, destination;
    cin >> source >> destination;
    addEdge(source, destination, nodes, i);
  }

  int userInput = 0;
  while (userInput != 3) {
    mainMenu();
    cin >> userInput;
    switch (userInput) {
      case 1:
        cout << "Enter the starting node for DFS: ";
        cin >> start;
        resetVisited(nodes);
        DFS(start, nodes);
        break;

      case 2:
        cout << "Enter the starting node for BFS: ";
        cin >> start;
        resetVisited(nodes);
        BFS(start, nodes);
        break;

      case 3:
        cout << "Exiting program.\n";
        userInput = 3;
        break;

      default:
        break;
    }
  }
  return 0;
}