Witam, moim zadaniem jest napisanie generatora grafu z krawędziami nieskierowanymi, przy zadanej liczbie wierzchołków (n) oraz wypełnieniu. Wypełnienie to stosunek istniejących krawędzi do maksymalnej liczby możliwych krawędzi w grafie, wyrażony w procentach. (liczba_krawędzi = n*(n-1)*wypełnienie/50)
Graf jest tablicą statyczną typu Graf, który jest strukturą. Póki co wymęczyłem taki kod:
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <fstream>
#include <cstdio>
#include <vector>
#include <set>
#define ZAKRES 1000000
using namespace std;
struct Graf
{
int wierzcholek1;
int wierzcholek2;
int waga;
};
Graf tablica_grafu[ZAKRES];
int n;
// funkcja exist sprawdza, czy w generowanym grafie znajduje sie juz krawedz, ktora chemy dodac
bool exist(int a, int b, int indeks)
{
for(int i = 0; i < indeks; i++)
{
if((tablica_grafu[i].wierzcholek1 == a && tablica_grafu[i].wierzcholek2 == b) ||
(tablica_grafu[i].wierzcholek1 == b && tablica_grafu[i].wierzcholek2 == a))
{
return 1;
}
}
return 0;
}
void Uzupelnij_Tablice_Losowo(int n, int wypelnienie)
{
// generowanie drzewa rozpinajacego, zeby graf byl spojny
srand((unsigned)time(NULL));
for(int i = 0; i < n; i++)
{
tablica_grafu[i].wierzcholek1 = i;
tablica_grafu[i].waga = rand() % 99 +1;
if(i < n-1)
tablica_grafu[i].wierzcholek2 = i+1;
if(i == n-1)
tablica_grafu[i].wierzcholek2 = rand() % (n-1) +1;
}
srand((unsigned)time(NULL));
// wypelnianie grafu losowymi polaczeniami
// n*(n-1)/2 - maksymalna liczba krawedzi
// -n zeby ominac n pozycji z drzewem rozpinajacym
for(int i = n; i < (n*(n-1)*wypelnienie/50); i++)
{
do
{
tablica_grafu[i].wierzcholek1 = rand() % (n-1) +1; // i+n bo n pierwszych miejsc to drzewo rozpinajace
// % (n-1) + 1 zeby nie bylo zerowych wag
do
{
tablica_grafu[i].wierzcholek2 = rand() % (n-1) +1;
}
while(tablica_grafu[i].wierzcholek1 == tablica_grafu[i].wierzcholek2); // kiedy jest rowne, ma powtorzyc
} // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1
while(exist(tablica_grafu[i].wierzcholek1,tablica_grafu[i].wierzcholek2,i-n)); // powtorz, jesli krawedz juz istnieje
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
tablica_grafu[i].waga = rand() % 99 +1;
}
}
void Wyswietl_Graf(int n, int wypelnienie)
{
for(int i=0; i<(n*(n-1)*wypelnienie/50); i++)
{
cout << tablica_grafu[i].wierzcholek1 << "\t"
<< tablica_grafu[i].wierzcholek2 << "\t"
<< tablica_grafu[i].waga << "\n";
}
}
int main()
{
n = 10;
int wypelnienie = 25;
Uzupelnij_Tablice_Losowo(n, wypelnienie);
Wyswietl_Graf(n, wypelnienie);
getchar();
}
Problem tkwi chyba w indeksie przekazywanym do funkcji 'exist'. Wszystko działa dla indeksu zaczynającego się od 0, czyli dla 'i-n'. Graf generuje się, ale mimo to pojawiają się połączenia skierowane, których miało nie być. I nic dziwnego, bo nie jest wówczas sprawdzana cała tablica z grafem, tylko jej część pomniejszona o n krawędzi.
Niestety, kiedy próbuję przekazać jako indeks pełną liczbę istniejących krawędzi, czyli 'i' program staje w miejscu, procek się grzeje i nie wyskakuje żaden seg fault ;/
Proszę o pomoc.