Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

szukanie sciezki w grafie

Ostatnio zmodyfikowano 2017-05-31 14:14
Autor Wiadomość
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ć

C/C++
#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()
{
   
    // -----------------------------------macierz sasiedztwa------
   
   
    odwiedzony = new bool[ V ];
    odwiedzony_szuk = new bool[ V ];
    tworzy_MS( mac_sas, V );
    odczyt_MS( mac_sas );
    // zawartosc_macierzy_sasiedztwa(mac_sas, V);
    DFS( mac_sas, 1 );
    // DFS(mac_sas,0);
   
    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;
        }
       
    }
    //cout<<V<<endl;
    liczenie.close();
    return V;
}

void DFS( int ** mac_sas, int wierzcholek )
{
    odwiedzony[ wierzcholek ] = true;
    //  cout<<wierzcholek<<endl;
    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;
    }
}
P-161853
darko202
» 2017-05-31 14:14:00
przeczytaj
http://www.algorytm.org​/algorytmy-grafowe​/przeszukiwanie-grafu-wszerz-bfs-i-w-glab-dfs.html
gdzie masz opisany algorytm DFS

niestety nie mogę Ci udzielić wskazówek co poprawić, bo nie masz żadnego algorytmu w DFS_szukaj
ot pusta wydmuszka :(
 
to jest Twoja praca i masz jakoś się przez to rozwinąć 
nawet jeśli będzie to znalezienie i przeanalizowanie gotowca
np. z
http://eduinf.waw.pl/inf/alg​/001_search/0125.php
P-161855
« 1 »
  Strona 1 z 1