Przeszukiwanie grafu w głąb - rekurencja
Ostatnio zmodyfikowano 2018-03-27 15:18
milmega Temat założony przez niniejszego użytkownika |
Przeszukiwanie grafu w głąb - rekurencja » 2018-03-26 22:32:21 Dobry wieczór, Poniższy kod ma za zadanie wypisywać liczbę wierzchołków w konkretnym podgrafie o korzeniu 'x'. Chcę to zrobić rekurencją, żeby po jednym wywołaniu funkcji mieć już w tablicy wszystkie ilości wierzchołków w podgrafie o korzeniu 'x'. Problem jest w tym, że funkcja daje złe wyniki dla podgrafów, które mają ponad jedno "piętro" (tzn. 1 jest ojcem 2 i 3, a 2 jest ojcem 4 i 5, to wtedy dla 1 wypisze jakąs dziwną liczbę) Cały graf jest skierowany od rodzica w stronę dzieci. Prosiłbym o wytłumaczenie mojego błędu. #include<iostream>
#include<list>
using namespace std;
int wierzcholki[ 10001 ];
list < int > tab[ 10001 ];
int vc = 0;
int ilosc( int korzen )
{
if( tab[ korzen ].size() == 0 )
{
wierzcholki[ korzen ] = 1;
return 1;
}
int wielkosc = tab[ korzen ].size();
for( int i = 0; i < wielkosc; i++ )
{
int neighs = tab[ korzen ].front();
tab[ korzen ].pop_front();
wierzcholki[ korzen ] += ilosc( neighs );
}
wierzcholki[ korzen ] ++;
}
int main()
{
ios_base::sync_with_stdio( false );
cin.tie( NULL );
int n, a, b;
cin >> n;
for( int i = 1; i < n; i++ )
{
cin >> a >> b;
tab[ a ].push_back( b );
}
ilosc( 1 );
int q, x;
cin >> q;
while( q-- )
{
cin >> x;
cout << wierzcholki[ x ] << '\n';
}
return 0;
}
|
|
pekfos |
» 2018-03-27 00:40:26 ilosc() niczego nie zwraca. |
|
milmega Temat założony przez niniejszego użytkownika |
» 2018-03-27 09:23:19 Chodzi o to, żeby funkcja uzupełnianiała tablice wierzchołki.
|
|
pekfos |
» 2018-03-27 10:31:05 wierzcholki[ korzen ] += ilosc( neighs );
|
Używasz wartości zwróconej z ilosc(). ilosc() niczego nie zwraca. |
|
milmega Temat założony przez niniejszego użytkownika |
» 2018-03-27 13:27:36 Wydaje mi się że jednak coś zwraca skoro dla niektórych wierzchołków zapisuje dobre wyniki w tabeli, ale mogę się mylić. |
|
milmega Temat założony przez niniejszego użytkownika |
» 2018-03-27 13:28:31 Jeśli ciągle nie mam rację to jak przerobić ta funkcję żeby zwracała to co chce? |
|
darko202 |
» 2018-03-27 15:10:38 1. wydaje mi się, że źle zapisujesz graf - ja tego nie widzę na kartce zapisz sobie dowolny graf i spróbuj go odtworzyć z utworzonych w programie struktur przeczytaj np. http://eduinf.waw.pl/inf/alg/001_search/0124.php2. jeśli deklarujesz że tworzysz funkcję która cos zwraca np. int fun()
{
int obliczenia, obliczenia2;
...
if(...)
return obliczenia;
...
return obliczenia2;
}
to musi mieć return na wszystkich ścieżkach w Twoim kodzie są ścieżki w funkcji, które nie kończą się return ... dlatego @pekfos pisze że funkcja nic nie zwraca. 3. używasz w programie zmiennych globalnych na razie masz jedną funkcję, ale przy wielu będzie skutkować to dziwnymi błędami z tego powodu używanie zmiennych globalnych jest złą praktyką 4. Naucz się techniki debugowania programu, aby oglądać jego działanie linia po linii w tym stan każdej zmiennej |
|
milmega Temat założony przez niniejszego użytkownika |
» 2018-03-27 15:18:10 Co do grafu to na 99% procent jestem pewny , że jest dobrze zapisany bo to poprostu zwykła lista sąsiedztwa z tym że sasiadami każdego wierzchołka są tylko jego dzieci. A co do reszty to coś spróbuje jescze wymyślić i dzięki za pomoc. |
|
| « 1 » |