Avoid infinite recursion in destructor

Question

As part of an exercise my university has tasked me with, I have written a small Graph implementation, following this header.

class Node {

private:
    std::string name;
    std::vector<Node*> children;

public:
    Node(const std::string& name="");
    virtual ~Node();

}

When writing code for the destructor ~Node(), I noticed that my implementation fails when the graph contains a cycle. This is my implementation so far, which obviously doesn't work if the graph contains a cycle.

Node::~Node() {
    for (Node* n : children) {
        delete n;
        n = NULL;
    }
    children.clear();
}

I am uncertain as to how I would most elegantly write a destructor that can handle cycles in the graph?

Please note that I was specifically tasked to write a recursive destructor. Thank you for your answers!

Answer 1

Option 1: Choose a representation for the graph where nodes are not owned by other nodes, but rather the graph which would be a distinct object. This way the node destructor doesn't need to do anything. _{This won't satisfy the requirement of recursion}:

struct Graph {
    std::vector<std::unique_ptr<Node>> nodes;
};

Note that if there is no inheritance involved, then you could simply use std::vector<Node>. I assume that there is, due to the usage of virtual desturctor in Node.

Alternatively, you could use another representation for the graph such as adjacency list.

Option 2: Use an algorithm to generate a minimum spanning forest of the graph. Then recursively delete the roots of each spanning tree. You can for example use the Kruskal's algorithm. (Given your representation, it looks like your graph may be connected, in which case there would be only one spaning tree).