dfswithstack.cpp

#include <iostream>
using namespace std;
/*
class Stack {
    int* arr;
    int top;
    int size;
public:
    Stack(int n) {
        size = n;
        arr = new int[size];
        top = -1;
    }

    void push(int val) {
        if (top < size - 1) {
            arr[++top] = val;
        }
    }

    int pop() {
        if (top == -1) {
            return -1;
        }
        return arr[top--];
    }

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

    ~Stack() {
        delete[] arr;
    }
};
*/

class Stack{
    int *arr;
    int top;
    int size;
    public:
    Stack(int n){
        size=n;
        arr=new int[size];
        top=-1;
    }
    void push(int val){
        if(top<size-1){
            arr[++top]=val;
        }
    }
    int pop(){
        if(top==-1){
            return -1;
        }else{
            return arr[top--];
        }
        
    }
    bool isEmpty(){
        return top==-1;
    }

    ~Stack(){
        delete[] arr;
    }

};

/*

void dfs(int** adj, int V, int start) {
    bool* visited = new bool[V];
    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }

    Stack st(V);
    st.push(start);

    while (!st.isEmpty()) {
        int node = st.pop();

        if (!visited[node]) {
            cout << node << " ";
            visited[node] = true;

            // Push neighbors in reverse order if you want smaller ones to come first
            for (int i = V-1; i >= 0; i--) {
                if (adj[node][i] == 1 && !visited[i]) {
                    st.push(i);
                }
            }
        }
    }

    delete[] visited;
}
*/

void dfs(int **adj,int vertices,int start){
    bool* visited=new bool[vertices];
    for(int i=0;i<vertices;i++){
        visited[i]=false;
    }

    Stack st(vertices);
    st.push(start);
    visited[start]=true;
    while(!st.isEmpty()){
        int node=st.pop();
        cout<<node<<" ";
        
        for(int i=vertices-1;i>=0;i--){
            if(adj[node][i]==1 && !visited[i]){
                st.push(i);
                visited[i]=true;
            }
        }
    }
    delete[] visited;
}

int main() {
    int V, E;
    cout << "Enter number of vertices and edges: ";
    cin >> V >> E;

    int** adj = new int*[V];
    for (int i = 0; i < V; i++) {
        adj[i] = new int[V];
        for (int j = 0; j < V; j++) {
            adj[i][j] = 0;
        }
    }

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

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

    cout << "DFS Traversal: ";
    dfs(adj, V, start);
    cout << endl;

    for (int i = 0; i < V; i++) {
        delete[] adj[i];
    }
    delete[] adj;

    return 0;
}