szukanie sciezki w grafie
Ostatnio zmodyfikowano 2017-05-31 14:14
mikewazowski Temat założony przez niniejszego użytkownika |
szukanie sciezki w grafie » 2017-05-31 13:43:14 potrzebuje pomocy w przerobieniu algorytm DFS tak by wyszukiwał ścieżkę w grafie zapisanym jako macierz sąsiedztwa, jak narazie wyszukuje jedynie drogę między 2 wierzchołkami, prosze o wskazówki co muszę poprawić #include <iostream> #include <fstream> #include <stack> #include <list> using namespace std;
int liczenie(); int V = liczenie(); int ** mac_sas = new int *[ V ]; void tworzy_MS( int ** mac_sas, int V ); int liczba_kraw = 0; void odczyt_MS( int ** mac_sas ); void zawartosc_macierzy_sasiedztwa( int ** mac_sas, int V ); void DFS( int ** mac_sas, int wierzcholek ); bool * odwiedzony; void DFS_szukaj( int ** mac_sas, int wierzcholek, int szukany ); bool * odwiedzony_szuk;
int main() { odwiedzony = new bool[ V ]; odwiedzony_szuk = new bool[ V ]; tworzy_MS( mac_sas, V ); odczyt_MS( mac_sas ); DFS( mac_sas, 1 ); int A, B; cin >> A; cin >> B; A = A - 1; B = B - 1; DFS_szukaj( mac_sas, A, B ); return 0; }
int liczenie() { int V = 0; ifstream liczenie; liczenie.open( "graph.txt" ); char znak; while( liczenie >> znak ) { if( znak == ':' ) { ++V; cout << "dziala" << endl; } } liczenie.close(); return V; }
void DFS( int ** mac_sas, int wierzcholek ) { odwiedzony[ wierzcholek ] = true; for( int i = 0; i < V; i++ ) { if( mac_sas[ wierzcholek ][ i ] == 1 && !odwiedzony[ i ] ) DFS( mac_sas, i ); } } void DFS_szukaj( int ** mac_sas, int wierzcholek, int szukany ) { odwiedzony_szuk[ wierzcholek ] = true; for( int i = 0; i < V; i++ ) { if( mac_sas[ wierzcholek ][ szukany ] == 1 ) cout << "jest sciezka" << endl; else cout << "nie ma" << endl; } } void tworzy_MS( int ** mac_sas, int V ) { for( int i = 0; i < V; i++ ) { mac_sas[ i ] = new int[ V ]; } for( int i = 0; i < V; i++ ) { odwiedzony[ V ] = false; odwiedzony_szuk[ V ] = false; for( int j = 0; j < V; j++ ) { mac_sas[ i ][ j ] = 0; } } } void odczyt_MS( int ** mac_sas ) { fstream plik; plik.open( "graph.txt" ); int Ve, E; char dwukropek; if( plik.is_open() ) { while( plik.good() ) { plik >> Ve; plik >> dwukropek; while(( plik.get() != '\n' ) && !plik.eof() ) { plik >> E; mac_sas[ Ve - 1 ][ E - 1 ] = 1; liczba_kraw++; } } } else if( plik.eof() ) std::cout << "Koniec pliku"; else if( plik.fail() ) std::cout << "Blad wczytania pliku"; plik.close(); } void zawartosc_macierzy_sasiedztwa( int ** mac_sas, int V ) { cout << "MACIERZ SASIEDZTWA" << endl; for( int i = 0; i < V; i++ ) { for( int j = 0; j < V; j++ ) { std::cout << mac_sas[ i ][ j ]; } std::cout << std::endl; } }
|
|
darko202 |
» 2017-05-31 14:14:00 |
|
« 1 » |