BFS – Parcurgerea in latime

Prin parcurgerea grafului G se întelege vizitarea, tuturor nodurilor, plecând de la un nod de plecare, vizitand in mod progresiv fiecare nod al grafului. Probabil ati auzit pana acum de DFS sau BFS

Un graf poate fi parcurs în următoarele două moduri:

• în adâncime (DFS = Depth First Search)
• în lătime (BFS = Breadth First Search)

Am prezentat deja parcurgerea in adancime, asa ca astazi o sa discutam despre parcurgerea in latime (BFS).

Memorarea vecinilor

Vom folosii libraria #include <vector> pentru a utiliza vectori alocati dinamic. Explicatia o gasiti in articol.

#include <vector>
const int NLIM = 100005;
vector < int > Edge[NLIM];

De data aceasta vom avea de a face cu un graf orientat (problema BFS – infoarena.ro) asa ca vom stoca doar un singur sens. Avem grija desigur sa citim bine fisierul de intrare.

Edge[x].push_back(y);

Folosirea cozii

Deoarece algoritmul BFS parcurge mai intai toate nodurile de acelasi nivel (adica “toti vecinii deodata”), avem nevoie sa folosim o coada pentru a retine nodurile ce urmeaza a fi parcurse.

#include    <queue>
queue <int> Coada;
Coada.push(NodStart);

Algoritmul BFS

Declaram vectorul global “Distanta” in care Distanta[i] va reprezenta distanta de la nodul de start la nodul numarul i.

void BFS()
{
    int Nod, Vecin;
    while(!Coada.empty())
    {
        Nod =  Coada.front();
        Coada.pop();
        for(unsigned int i = 0; i < Edge[Nod].size(); i++)
        {
            Vecin = Edge[Nod][i];
            if(Distanta[Vecin] == -1)
            {
                Coada.push(Vecin);
                Distanta[Vecin] = Distanta[Nod] + 1;
            }
        }
    }
}

Primul lucru in algloritmul BFS va fi intotdeauna sa luam primul nod din coada si sa-l analizam. Functia front() preia primul element din coada, in timp ce functia pop il sterge din coada. Mai multe detalii despre clasa <queue>, gasiti aici: Coada C++.

Dupa ce am preluat nodul curent din coada, ii punem toti vecinii in coada si le calculam distanta.

La final dupa ce am parcurs toate nodurile, afisam distanta pentru fiecare nod in parte.

for(int i = 1; i <= N; i++)
    fout << Distance[i] << " ";

Tot algoritmul pentru obtinerea celor 100 de puncte pe infoarena.ro poate fi gasit mai jos:

#include    <iostream>
#include    <fstream>
#include    <vector>
#include    <queue>

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

const int NLIM = 100005;

int N, M, S;
int Distance[NLIM];

vector <int> Edge[NLIM];
queue <int> Q;

void BFS()
{
    int Node, Next;
    while(!Q.empty())
    {
        Node =  Q.front();
        Q.pop();
        for(unsigned int i = 0; i < Edge[Node].size(); i++)
        {
            Next = Edge[Node][i];
            if(Distance[Next] == -1)
            {
                Q.push(Next);
                Distance[Next] = Distance[Node] + 1;
            }
        }
    }
}

void Read()
{
    fin >> N >> M >> S;
    for(int i = 1; i <= M; i++)
    {
        int x, y;
        fin >> x >> y;
        Edge[x].push_back(y);
    }
    for(int i = 1; i <= N; i++)
        Distance[i] = -1;
    Distance[S] = 0;

    Q.push(S);

    BFS();

    for(int i = 1; i <= N; i++)
        fout << Distance[i] << " ";
}

int main()
{
    Read();
    return 0;
}