C++ generowanie grafu spójnego (przeszukiwania w głąb DFS) Segmentation fault
: 08 grudnia 2012, 21:09
Witajcie
Mam mały problem z generowaniem grafu spójnego dla zadanej wartości liczby wierzchołków. Graf potrzebny jest mi do badania czasu potrzebnego do wyznaczania najmniejszego drzewa spinającego algorytmami Kruskala i Prima. Idea programu jest taka aby wygenerować graf spójny generuje losowy graf o losowym wypełnieniu po czym sprawdzam go algorytmem dfs jeśli wszystkie wierzchołki zostaną odwiedzone graf jest spójny, jeśli zaś zostanie jakikolwiek wierzchołek nieodwiedzony generujemy graf od początku po czym wykonujemy jeszcze raz algorytm dfs. Program wydaje mi się że działa prawidłowo dla wierzchołków z zakresu 4-15 przy liczbie wierzchołków powyżej 15 wysypuje mi błąd Segmentation fault.
Przy debugowaniu przekraczam pamięć w linii 66 (w kodzie wyżej pogrubiona). Czy mógłby mi ktoś pomóc znaleźć błąd w kodzie bądź nakierować dlaczego powyżej wartości 15 program zaczyna sypać błędy ? Potrzebuję aby graf był generowany w przybliżeniu do 1000 wierzchołków.
Czy jeśli ta implementacja jest do niczego można ten program napisać w jakiś prosty/lepszy sposób ?
Mam mały problem z generowaniem grafu spójnego dla zadanej wartości liczby wierzchołków. Graf potrzebny jest mi do badania czasu potrzebnego do wyznaczania najmniejszego drzewa spinającego algorytmami Kruskala i Prima. Idea programu jest taka aby wygenerować graf spójny generuje losowy graf o losowym wypełnieniu po czym sprawdzam go algorytmem dfs jeśli wszystkie wierzchołki zostaną odwiedzone graf jest spójny, jeśli zaś zostanie jakikolwiek wierzchołek nieodwiedzony generujemy graf od początku po czym wykonujemy jeszcze raz algorytm dfs. Program wydaje mi się że działa prawidłowo dla wierzchołków z zakresu 4-15 przy liczbie wierzchołków powyżej 15 wysypuje mi błąd Segmentation fault.
Kod: Zaznacz cały
#include <iostream>
#include <stdlib.h>
#include <vector> //STL
#include <stack> //STL
using namespace std;
void dfs(int wierzcholek,int Odwiedzony[],int liczba_wierzcholkow);
int przegladanie_w_glab(int liczba_wierzcholkow, int **tablica_lokalna);
int nastepnik_dfs(int wierzcholek,int **graf, int Odwiedzony[], int liczba_wierzcholkow);
void wyswietl_graf_spojny_dwa(int liczba_wierzcholkow, int **tablica_lokalna);
int generuj_graf_spojny_dwa(int liczba_wierzcholkow);
int **tablica_globalna;
int proba=1,liczba_wierzcholkow;
stack< int,vector<int> > stos;
int main()
{
cout <<"liczba wieczcholkow: ";
cin >> liczba_wierzcholkow;
generuj_graf_spojny_dwa(liczba_wierzcholkow);
przegladanie_w_glab(liczba_wierzcholkow, tablica_globalna);
return 0;
}
//Jeśli procedura wywołana dla pierwszego wierzchołka "dotrze" do wszystkich wierzchołków grafu to graf jest spójny.
int przegladanie_w_glab(int liczba_wierzcholkow, int **tablica_lokalna)
{
int Odwiedzony[liczba_wierzcholkow]; //tablica w której zapisujemy odwiedzone wierzchołki zaznaczamy je "1"
//zerowanie tablizy odwiedzonych wierzchołków
for (int i=0; i<liczba_wierzcholkow; i++) Odwiedzony[i]=0;
// Algoryt przeszukiwanie w głąb DFS
dfs(0,Odwiedzony,liczba_wierzcholkow);
// jeśli suma wszystkich komórek Odwiedzone da nam liczbę wierzchołków to graf jest spójny
int spojnosc=0;
for(int i=0; i<liczba_wierzcholkow; i++)
{
spojnosc=spojnosc+Odwiedzony[i];
}
if(spojnosc==liczba_wierzcholkow)
{
cout << endl << "Wygenerowany graf jest grafem SPOJNYM (sprawdzono algorytmem DFS)"
<<endl << "Wygenerowano za podejściem: "<<proba<<endl;
}
else
{
proba++;
generuj_graf_spojny_dwa(liczba_wierzcholkow);
przegladanie_w_glab(liczba_wierzcholkow,tablica_globalna);
}
return 0;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//Funkcja zwraca OSTATNI nieodwiedzony nastepnik wierzcholka
int nastepnik_dfs(int wierzcholek,int **graf, int Odwiedzony[], int liczba_wierzcholkow)
{
for (int i=liczba_wierzcholkow-1; i>0; i--)
{[B]
if ( (graf[i][wierzcholek] != 0) && (Odwiedzony[i]==0) )[/B]
{
Odwiedzony[i]=1;
return(i);
}
}
//Wierzcholek nie ma juz nastepnikow do odwiedzenia
return(-1);
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void dfs(int wierzcholek,int Odwiedzony[],int liczba_wierzcholkow)
{
int u,nastepny;
Odwiedzony[wierzcholek]=1;
nastepny=nastepnik_dfs(wierzcholek,tablica_globalna,Odwiedzony,liczba_wierzcholkow);
while (nastepny!=-1)
{
stos.push(nastepny);
nastepny=nastepnik_dfs(wierzcholek,tablica_globalna,Odwiedzony,liczba_wierzcholkow);
}
if (!stos.empty())
{
u=stos.top();
stos.pop();
dfs(u,Odwiedzony,liczba_wierzcholkow);
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int generuj_graf_spojny_dwa(int liczba_wierzcholkow)
{
int krawedzie,procent,wygenerowane_krawedzie=0,licznik=1;
//tworzy dynamiczną dwuwymirową tablicę o rozmiarach n x n
int **tablica_lokalna = new int*[liczba_wierzcholkow]; //szerokość
for (int x=0; x<liczba_wierzcholkow; x++)
{
tablica_lokalna[x] = new int[liczba_wierzcholkow]; //wysokość
}
//zerowanie tablicy
for(int i=0; i<liczba_wierzcholkow; i++)
{
for(int j=0; j<=i; j++)
{
tablica_lokalna[i][j]=tablica_lokalna[j][i]=0;
}
}
//wypełnia losowymi wartościami tablicę w miejscu (i,i) wsyawiamy zera bo krawędź nie istnieje
//nie ma pętli wychodzących z ptk(i) i wracających do ptk(i) oraz puknty (a,b) i (b,a) mają taką samę wagę
srand((unsigned)time(NULL));
for(int i=0; i<liczba_wierzcholkow; i++)
{
for(int j=0; j<=i; j++)
{
if(j==i) tablica_lokalna[i][j]=0;
else
{
tablica_lokalna[i][j] = tablica_lokalna[j][i] = rand() % 4;
licznik++;
}
}
}
//liczymy wypełnienie
for(int i=0; i<liczba_wierzcholkow; i++)
{
for(int j=0; j<=i; j++)
{
if(tablica_lokalna[i][j]!=0) wygenerowane_krawedzie++;
}
}
krawedzie=liczba_wierzcholkow*(liczba_wierzcholkow-1)*0.5;
procent=(wygenerowane_krawedzie*100/krawedzie);
if(procent==100) generuj_graf_spojny_dwa(liczba_wierzcholkow);
cout << endl << "Wypełenienie wygenerowanego grafu to: "<<procent<<"%"<<endl<<endl;
tablica_globalna=tablica_lokalna;
//wyświatlamy tablicę
wyswietl_graf_spojny_dwa(liczba_wierzcholkow,tablica_globalna);
//usuwa tablicę dwuwymiarową
for(int x=0; x<liczba_wierzcholkow; x++) delete [] tablica_lokalna[x];
delete []tablica_lokalna;
return 0;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void wyswietl_graf_spojny_dwa(int liczba_wierzcholkow, int **tablica)
{
for(int i=0; i<liczba_wierzcholkow; i++)
{
cout <<"\t\t";
for(int j=0; j<liczba_wierzcholkow; j++)
{
cout << tablica[i][j]<<" ";
}
cout << endl;
}
}
Czy jeśli ta implementacja jest do niczego można ten program napisać w jakiś prosty/lepszy sposób ?