Generowanie spójnego grafu o zadanej liczbie wierzchołków

Jak w temacie, kompletnie nie wiem jak sie do tego zabrać, temat widzę, że był poruszany na forum jednak znalezione w necie kody nic mi nie mówią.
Nie pogardzę gotowym kodem.

1. Losujesz dowolny węzeł i wrzucasz do kolekcji S
2. Pozostałe węzły wrzucasz do kolekcji L
3. Losujesz węzeł Wy z kolekcji S oraz węzeł Wx z kolekcji L
4. Łączysz wylosowane węzły Wy,Wx krawędzią
5. Przerzucasz węzeł Wx do kolekcji S
6. Jeżeli kolekcja L nie jest pusta wróć do punktu 3.

Masz wylosowane minimalne drzewo rozpinające, możesz dolosować jeszcze kilka krawędzi.

Dowolnego grafu? Skierowanego/Nieskierowanego? Ma spełniać jakieś dodatkowe własności?

To co podajesz w takiej wersji jest trywialne. Najprostszy spójny graf o N wierzchołkach to po prostu na przykład

A <-> B <-> C <-> D <-> E ... <-> Z

(gdzie A, B, C... to wierzchołki, a <-> to krawędzie).

Jeśli graf ma mieć element losowy, można następnie pododawać (dużo) losowych krawędzi.

Jeśli nie pogardzisz gotowym kodem to proszę, ciekawe czy Ci w czymś pomoże ;].

struct node {
    vector<int> edges;
};

int main() {
    int n = 10;
    vector<node> graph(n);
    for (int i = 0; i < n - 1; i++) {
        graph[i].edges.push_back(i + 1);
        graph[i + 1].edges.push_back(i);
    }
}