dfs.cpp

#include <iostream>
using namespace std;

void dfs(int **graph, int start, int n) {
    bool *visited = new bool[n]{false};  // Dynamic allocation for visited array
    int *stack = new int[n];  // Dynamic allocation for stack
    int top = -1;
    stack[++top] = start;
    visited[start] = true;

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

        for (int i = 0; i < n; i++) {
            if (graph[node][i] == 1 && !visited[i]) {
                stack[++top] = i;
                visited[i] = true;
            }
        }
    }

    // Free dynamically allocated memory
    delete[] visited;
    delete[] stack;
}

int main() {
    int n, start;
    cout << "Enter number of nodes: ";
    cin >> n;

    // Dynamically allocate the adjacency matrix
    int **graph = new int*[n];
    for (int i = 0; i < n; i++) {
        graph[i] = new int[n]();
    }

    cout << "Enter the adjacency matrix (0 or 1 for each pair of nodes):" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }

    cout << "Enter the starting node for DFS: ";
    cin >> start;

    dfs(graph, start, n);

    // Free dynamically allocated memory for the graph
    for (int i = 0; i < n; i++) {
        delete[] graph[i];
    }
    delete[] graph;

    return 0;
}