Program crashes while freeing dynamically allocated memory

Question

I'm representing a graph using an adjacency list here.

Here is the code:

// A program to check the reachability between two nodes within a specified number of steps using an adjacency list
/***************************************************************************/

#include <iostream>
#include <fstream>

using namespace std;

struct node {
    int value;
    node* next;

    // Constructors:
    node() {
        value = 0;
        next = 0;
    }
    node(int x) {
        value = x;
        next = 0;
    }
};


node* al; // Adjacency list
int n; // Number of nodes
int node1, node2, k; // For reading input from the console
int counter;

bool checkReachability(int, int, int);
void freeMemory();

int main() {

    ifstream in;
    in.open("Input.txt");
    if(in) {
        in >> n;
        al = new node[n];
        for (int i = 0; i < n; i++) {
            al[i].value = i+1;
        }

        int a, b;
        while(in >> a >> b) {
            node* temp = &al[a-1];
            while(temp->next != 0) {
                temp = temp->next;
            }
            temp->next = new node(b);    
        }

        cout << "\n\nThe adjacency list representation of the graph is as follows: \n";
        cout << "________________________________\n\n";
        for (int i = 0; i < n; i++) {
            cout << al[i].value;
            node* temp = al[i].next;
            while(temp != 0) {
                cout << "->" << temp->value;
                temp = temp->next;
            }
            cout << endl;
        }
        cout << "________________________________\n";
        in.close();
        char c;
        do {
            cout << "\nPlease enter the input (node1, node2, k): \n";
            cin >> node1 >> node2 >> k;
            counter = 0;
            if (checkReachability(node1 - 1, node2, k)) {
                cout << "\nReachable within " << k << " steps";
                if (counter < k) {
                    cout << " (actually " << counter << ")";
                }
                cout << endl << endl;
            }
            else {
                cout << "\nNot reachable within " << k << " steps  \n";
            }
            cout << "\nDo you want to continue? Y/N \n\n";
            cin >> c;
        } while (c == 'Y' || c == 'y');
        freeMemory();
    } else {
        cout << "\nCouldn't find the input file\n\n";
    }
    return 0;
}

bool checkReachability(int n1, int n2, int k) {
    if ((n1 + 1) == n2) return true;
    counter++;
    if (counter <= k) {
        node* temp = &(al[n1]);
        while (temp != 0) {
            if (temp->value == n2) return true;
            temp = temp->next;
        }
        temp = al[n1].next; 
        while (temp != 0) {
            if (checkReachability(((temp->value)-1),n2,k)) return true;
            counter--;
            temp = temp->next;
        }   
    }
    return false;
}

void freeMemory() {
    cout << "\nFreeing memory...\n";
    // To free the dynamically allocated memory on the heap
    for (int i = 0; i < n; i++) {
        node* temp = &al[i];
        while(temp != 0) {
            node* temp2 = temp;
            temp = temp->next;
            delete temp2;
        }
    }
    //delete [] al;
    cout << "\nMemory freed.\n";
}

The program runs just fine. It's only when I choose to exit it, which calls the freeMemory function that it crashes. Please help me figure out what the problem is.

Input.txt file:

5
1 2
2 5
3 4
1 3

Output:

The adjacency list represent
____________________________

1->2->3
2->5
3->4
4
5
____________________________

Please enter the input (node
1 2 1

Reachable within 1 steps


Do you want to continue? Y/N

y

Please enter the input (node
2 4 4

Not reachable within 4 steps

Do you want to continue? Y/N

N

Freeing memory...

And then, it crashes.

Answer 1

This is wrong:

void freeMemory() {
    cout << "\nFreeing memory...\n";
    // To free the dynamically allocated memory on the heap
    for (int i = 0; i < n; i++) {
        node* temp = &al[i]; // HERE
        while(temp != 0) {
            node* temp2 = temp;
            temp = temp->next;
            delete temp2;
        }
    }
    delete [] al;
    cout << "\nMemory freed.\n";
}

The initial vector a1 is allocated via new node[n]. Meaning the initial entries in all slots a1[0...n-1] are part of the vector allocation; not part of the chained adjacency sequences associated to each node thereafter. I believe you need to do this:

void freeMemory() {
    cout << "\nFreeing memory...\n";
    // To free the dynamically allocated memory on the heap
    for (int i = 0; i < n; i++) {
        node* temp = al[i].next; // start with next pointer
        while(temp != 0) {
            node* temp2 = temp;
            temp = temp->next;
            delete temp2;
        }
    }
    delete [] al;
    cout << "\nMemory freed.\n";
}

Alternatively, you could use a pointer array from inception and dynamically single-allocate all nodes, not just the adjacency chains, at which time your loop for freeing would work, but the rest of your code would need some alteration. Given how far you are along with this, I'd just make the change I show above and call it good.