Hello!

I just want to ask you guys if anyone can help me reedit my program from BFS to DFS. I know how BFS works but i can't figure it out how to write the sintax. So i would please ask you guys if you could help me out.

Heres code of my last program:

#include <iostream>
#include <queue>
using namespace std;

const int bela = 0;
const int siva = 1;
const int crna = 2;
const int nil = -1;
const int inf = 2147483647;

char menu() {

    cout << "Iskanje z razvijanjem v sirino - izbira:";
    cout << "1 Vnos podatkov - rocni\n";
    cout << "2 Zagon algoritma Iskanje z razvijanjem v sirino\n";
    cout << "3 Izpis poti med vozliscem s in d\n";
    cout << "4 Konec\n";
    cout<<endl;
    cout << "Vasa izbira: ";
}

void vpis(int* matrika, int velikost) 
{
    cout << "Vpisi podatke" << endl;
    int v = velikost*velikost;
    for(int i=0; i<v; i++) 
    {
        cin >> matrika[i];
    }
    cout << endl;
}


void iskanjeVSirino(int* matrika, int* barva, int* razdalja, int* predhodnik, int velikost, int s) 
{
    queue<int> Q; 


    for(int i=0; i<velikost; i++) 
    {
        barva[i] = bela;
        razdalja[i] = inf; 
        predhodnik[i] = nil;
    }


    barva[s] = siva; 
    razdalja[s] = 0; 
    Q.push(s); 


    while(Q.empty() == false) 
    {
        int v = Q.front(); 
        Q.pop();

        int ePrvi = v*velikost; 
        int eZadnji = ePrvi+velikost; 
        for(int e=ePrvi; e<eZadnji; e++) 
        {
            if(matrika[e] == 1) 
            {
                int u = e-ePrvi;
                if(barva[u] == bela) 
                {
                    barva[u] = siva; 
                    razdalja[u] = razdalja[v]+1;
                    predhodnik[u] = v;
                    Q.push(u);
                }
            }
        }
        barva[v] = crna;
    }
}


void izpisPoti(int* razdalja, int* predhodnik, int s, int v) 
{
    if(v == s) 
    {
        cout << "vozlisce " << s << ": globina: " << razdalja[s] << endl;
    } else if(predhodnik[v] == nil) 
    {
        cout << "med " << s << " in " << v << " ni poti" << endl;
    } else 
    {
        izpisPoti(razdalja, predhodnik, s, predhodnik[v]);
        cout << "vozlisce " << v << ": globina: " << razdalja[v] << endl;
    }
}

int main() 
{
    int* matrika;
    int* barva;
    int* razdalja;
    int* predhodnik;
    int velikost = 0;
    int s;
    int v;

    bool running = true;
    char izbira;

    do 
    {
        menu(); 
        cin>>izbira;
        if(izbira=='1'){
            cout << "Vpisi zeljeno velikost matrike" << endl;
            cin >> velikost;
            matrika = new int[velikost*velikost];
            barva = new int[velikost];
            razdalja = new int[velikost];
            predhodnik = new int[velikost];         
            vpis(matrika, velikost);
        }
        else if(izbira=='2'){        
            if(velikost == 0) 
            {
                cout << "Najprej vpisi podatke" << endl;
            }
            else 
            {
                cout << "Vpisi zacetno vozlisce (0 - " << velikost-1 << ")" << endl;
                cin >> s;
                if(s >= velikost) 
                {
                    cout << "Napaka: vozlisce ne obstaja";
                    return 0;
                }
                iskanjeVSirino(matrika, barva, razdalja, predhodnik, velikost, s);
            }
        }
        else if(izbira=='3'){ 
            if(velikost == 0) 
            {
                cout << "Najprej vpisi podatke" << endl;
            }
            else 
            {
                cout << "Vpisi koncno vozlisce" << endl;
                cin >> v;
                if(v >= velikost) 
                {
                    cout << "Napaka: vozlisce ne obstaja";
                    return 0;
                }
                izpisPoti(razdalja, predhodnik, s, v);
                for(int i=0; i<velikost; i++) 
                {
                    cout << (char)((int)'A'+i) << " " << razdalja[i] << " " << (char)((int)'A'+predhodnik[i]) << endl;
                }
            }
        }                  
        else if(izbira=='4'){
            running = false;
        }
        else
            cout << "Napacna izbira!\n";
    }

    while (running);

    delete[] matrika;
    delete[] barva;
    delete[] razdalja;
    delete[] predhodnik;
    system ("PAUSE");
    return 0;
}

Sorry that the code is not in english, hope it doesn't make a difference.

Thanks again!

The main difference between a depth first search and a breadth first search is what data type you use to store your nodes. In a breadth first search you use a queue, in a depth first search you use a stack. Basically a queue is like a line-up, you put things in the back and take things out the front. A stack is like a deck of cards, you put things on the top and take things off the top. Both algorithms are identical in all other aspects so you can google either of them to get the required pseudocode.

This article has been dead for over six months. Start a new discussion instead.