Przeszukiwanie grafu w głąb - rekurencja
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!

Przeszukiwanie grafu w głąb - rekurencja

AutorWiadomość
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.

C/C++
#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;
}
P-170288
» 2018-03-27 00:40:26
ilosc() niczego nie zwraca.
P-170289
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.
P-170290
» 2018-03-27 10:31:05
C/C++
wierzcholki[ korzen ] += ilosc( neighs );
Używasz wartości zwróconej z ilosc(). ilosc() niczego nie zwraca.
P-170291
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ć.
P-170299
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?
P-170300
» 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.php

2.
jeśli deklarujesz że tworzysz funkcję która cos zwraca
np.
C/C++
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


P-170302
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.
P-170303
« 1 »
 Strona 1 z 1