Dzień dobry,
Program przechodzi w sposób BFS listę następników losowanego grafu. Wszystko działa niby prawidłowo (więc tutaj wielkich zmian nie potrzebuję, chociaż pewnie poziom programowania jest kiepski i mozna to zrobić 100 razy łatwiej), ale program wiesza się przy 128 (i więcej) elementach, co by oznaczało jakieś ograniczenia nadawane przez int. Jednak wszystkie zmienne są deklarowane jako unsigned long int (przynajmniej ja innych nie znalazłam). Skąd w takim razie to ograniczenie? Z góry dziękuję za pomoc.
Kod (niektóre fragmenty są wycięte):
#include <stdio.h>
#include <time.h>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <queue>
const long int maxn=1000000;
using namespace std;
unsigned long int **mac;
bool v[maxn];
unsigned long int r;
queue <unsigned long int> kolejka;
unsigned long int licznik=0;
typedef struct lista //element listy jednokierunkowej
{
unsigned long int liczba;
struct lista *next;
struct lista *prev;
}Lista;
lista **LN; //lista nastepnikow
class Graf
{
unsigned long int n;
public:
Graf(unsigned long int w)
{
n=w;
}
void tworzymygrafy ()
{
cout<<"--------TWORZENIE MACIERZY SASIEDZTWA--------------";
unsigned long int x,y,i,j,m;
srand(time(0));
mac=new unsigned long int*[n];
for(i=0;i<n;i++)
{
mac[i]=new unsigned long int[n];
}
m=n*(n-1)*0.25; // ile ma byc krawedzi
cout<<"Ilosc krawedzi: "<<m<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
mac[i][j]=0;
}
}
for(i=0;i<m;i++)
{
x=rand()%n;
y=rand()%n;
if (mac[x][y]==0 && (x!=y))
{
mac[x][y]=1;
}
else i--;
}
/*for(i=0;i<n;i++)
{
printf("\n");
for(j=0;j<n;j++)
{
printf("%d ", mac[i][j]);
}
}*/
cout<<"------TWORZENIE LISTY NASTEPNIKOW--------------";
lista *kon, *nowy, *listapom;
LN= new lista*[n];
listapom= new lista[1];
kon =new lista [1];
for(i=0; i<n; ++i)
{
LN[i]=NULL;
}
for(i=0; i<n; ++i)
{
cout<<"i:"<<i;
for(j=0; j<n; ++j){
if (mac[i][j]==1)
{ nowy = new lista[1];
nowy->liczba = j;
nowy->next = NULL;
if (LN[i] == NULL){
LN[i] = nowy;
listapom->liczba=j;
listapom->next=nowy;
nowy->prev=listapom;
cout<<"->"<<j;
}
else
{
kon->next = nowy;
nowy->prev=kon;
cout<<"->"<<nowy->liczba;
}
kon = nowy;
}
}cout<<endl;
}
}
};
//--------BFS----------------------------
int lbfscel (unsigned long int element, unsigned long int n)
{
if (v[element]==false) //jezeli element jeszcze nie byl odwiedzony
{
lista *it;
it=LN[element];
v[element]=true;
if (it==NULL)
return 1;
//cout<<"\n"<<it->liczba;
if (v[it->liczba]==false) kolejka.push(it->liczba);
while (it->next!=NULL)
{
if (v[it->next->liczba]==false)
{//cout<<"->"<<it->next->liczba;
kolejka.push(it->next->liczba);
}
it=it->next;
}
}
return 0;
}
int lbfs (unsigned long int p, unsigned long int n)
{
kolejka.push(p);
lbfscel(p, n);
v[p]=true;
if (LN[p]==NULL)
return 0;
else
{
unsigned long int *wolny, licznik=0;
wolny=&kolejka.front();
while (v[*wolny]==1)
{
if (licznik==n) return 0;
wolny++;
licznik++;
}
lbfs(*wolny, n);
v[*wolny]=true;
}
return 0;
}
int main ()
{
unsigned long int *q;
unsigned long int w;
unsigned long poczatek, koniec;
cout<<"Podaj ilosc elementow do grafu: ";
cin>>w;
Graf drzewo(w);
drzewo.tworzymygrafy();
cout<<"---------LISTA NASTEPNIKOW-------------------------";
for (unsigned long int i=0; i<w; i++)
v[i]=false;
poczatek=clock();
for (unsigned long int o=0; o<w; o++) //robienie lbfs w petli, zeby odwiedzic na pewno wszystkie elementy, nawet nie zwiazane krawedziamy z innymi
{
//cout<<"robie dla "<<o<<endl;
if (v[o]==false)
lbfs(o, w);
}
unsigned long int k=kolejka.size(); //tutaj kwestia techniczna, bo sie co nieco powtarzalo, wiec usuwamy powtorzenia :)
unsigned long int T[k];
for (unsigned long int p=0; p<k; p++)
{
//cout<<"\n"<<kolejka.front();
T[p]=kolejka.front();
kolejka.pop();
}
unsigned long int h=0;
for(int f=0;f<k;++f)
{
bool UnikalnaWartosc=true;
for(unsigned long int j=0;(j<f)&&(UnikalnaWartosc);++j) UnikalnaWartosc=(T[j]!=T[f]);
if(UnikalnaWartosc)
{
if(h<f) T[h]=T[f];
++h;
}
}
koniec=clock();
czas=(koniec-poczatek)/(double)CLOCKS_PER_SEC;
cout<<"Czas dla BFS listy nastepnikow to: "<<czas<<" sekund\n\n"<<endl;
system ("PAUSE");
return 0;
}