BFS and DFS Traversal

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// ---------------------- BFS FUNCTION ----------------------
void bfs(int start, vector<vector<int>>& adj, int n) {
    vector<bool> visited(n, false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    cout << "BFS Traversal: ";

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";

        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
    cout << endl;
}

// ---------------------- DFS FUNCTION ----------------------
void dfsUtil(int node, vector<vector<int>>& adj, vector<bool>& visited) {
    visited[node] = true;
    cout << node << " ";

    for (int neighbor : adj[node]) {
        if (!visited[neighbor])
            dfsUtil(neighbor, adj, visited);
    }
}

void dfs(int start, vector<vector<int>>& adj, int n) {
    vector<bool> visited(n, false);
    cout << "DFS Traversal: ";
    dfsUtil(start, adj, visited);
    cout << endl;
}

// ---------------------- MAIN ----------------------
int main() {
    int n, e;
    cout << "Enter number of vertices: ";
    cin >> n;

    cout << "Enter number of edges: ";
    cin >> e;

    vector<vector<int>> adj(n); // adjacency list

    cout << "Enter edges (u v):\n";
    for (int i = 0; i < e; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u); // for undirected graph
    }

    int start;
    cout << "Enter starting vertex: ";
    cin >> start;

    cout << endl;
    bfs(start, adj, n);
    dfs(start, adj, n);

    cout << "\nTime Complexity (BFS/DFS): O(V + E)";
    cout << "\nSpace Complexity (BFS/DFS): O(V + E)\n";

    return 0;
}