losowanie grafu, a jego spójność

Witam

należy wylosować graf, który będzie stanowił 25% grafu pełnego. Graf pełny ma V(V-1)/2 krawędzi więc my musimy wylosować .25*V(V-1)/2 krawędzi. Problem wydaje się dosyć prosty: można losować z pewnym prawdopodobieństwem:

int p=25;
for(int i=0; i<V; i++)
   for(int j=i; j<V; j++)
      if(p>rand()%100) //sprawdzamy prawdopodobieństwo istnienia krawędzi
        macierz[i][j] = macierz[j][i] = rand()%100; //losowa waga

Kod może mieć błędy bo teraz go napisałem na szybko, ale mam nadzieję, że widać mniej więcej o co chodzi.

Problemem jest zapewnienie spójności grafu, która jest wymagana przez algorytmy grafowe: np. Kruskala i Prim'a. Takie losowanie grafu jak powyżej raczej nie gwarantuje spójności. Więc pytanie do Was jak taką spójność zapewnić?

Można teoretycznie wylosować krawędź pomiędzy każdą parą wierzchołków, ale chyba nie jest to najlepsze rozwiązanie, bo nasz graf powoli przestaje być losowy, a jedynie rozbudowywana jest pewna stała struktura grafu. Macie jakieś pomysły?

Ja bym na początku zrobił drzewo a dopiero później dołączał kolejne krawędzie. Tworzenie drzewa możesz zrobić na strukturze Find & Union(Struktura zbiorów rozłącznych). Na przykład w ten sposób(jeżeli mamy n wierzchołków):
n-1 razy wykonaj:
{
losuj dwie liczby dopóki wylosowane należą do tego samego zbioru.
dodaj krawędź między wylosowane wierzchołki i połącz zbiory.
}