Przeszukiwanie wszerz (BFS)

Oj, widzę, że dawno nikt się tą stronką nie zajmował, no to trzeba by coś napisać ;)

BFS - przeszukiwanie wszerz, co nam daje?? Przejdziemy sobie przez cały w ten sposób, że zaczniemy od źródła, potem odwiedzimy wszystkie wierzchołki w odległości 1 od źródła, następnie w odległości 2 itd.

Jak to robimy?? Ano idea o ile może na początku wydawać się dziwna, wcale nie jest taka trudna. Bierzemy sobie źródło, zaznaczamy jako odwiedzone, potem wrzucamy na kolejkę wszystkich sąsiadów, zaznaczając, że ich odległość od źródła wynosi o jeden więcej niż źródła (czyli jeden). Co teraz? bierzemy pierwsze z brzegu z kolejki i znowu, wrzucamy sąsiadów na kolejke, zaznaczamy ich odległość itd, i tak do usranej śmierci, lub aż nam się wszystko na kolejce skończy i tutaj czasem robią się problemy, bo zdarza się, że kolejka nie chce nam opustoszeć ;)

Tak czy siak, zaklepane wygląda to mniej więcej tak:

#include <queue>
 
int odleglosc[N];
 
void BFS(int v)
{
    odleglosc[v]=0;
    queue <int> kolejka;
    kolejka.push(v);
    while (!kolejka.empty())
    {
        int u=kolejka.front();
        kolejka.pop();
        wrzuc_wszystkich_sasiadow_na_kolejke();
    }
}

A jak wygląda wrzuc_wszystkich_sasiadow_na_kolejke()?? Zależy, jak mamy zapisany na wektorze graf, to wygląda to tak:

void wrzuc()
{
    for (int i=0; i<G[u].size(); i++)      //G[u] to vector, w którym są sąsiedzi wierzchołka, na którym się skupiamy
        if (odleglosc[G[u][i]]+1<odleglosc[u])     //G[u][i] to sąsiad wierzchołka u
        {
            kolejka.push(G[u][i]);
            odleglosc[G[u][i]]=odleglosc[u]+1;
        }
}
 
//albo jeśli mamy tablicę bool odwiedzony[]
 
void wrzuc()
{
    for (int i=0; i<G[u].size(); i++)      //G[u] to vector, w którym są sąsiedzi wierzchołka, na którym się skupiamy
        if (!odwiedzony[G[u][i])     //G[u][i] to sąsiad wierzchołka u
        {
            kolejka.push(G[u][i]);
            odleglosc[G[u][i]]=odleglosc[u]+1;
        }
}

Jeśli mamy np plansze o wielkości N x M elementów, to wygląda tak:

//troszki sie to rozni, wiec zamieszczam calego BFSa
struct wsp
{
    int x, y;
};
 
int odleglosc[N][M], odwiedzony[N][M];
 
inline void BFS(wsp v)
{
    queue <wsp> kolejka;
    kolejka.push(u);
    while (!kolejka.empty())
    {
        wsp v=kolejka.front(); kolejka.pop();
        if (v.x+1<=M && !odwiedzony[G[v.y][v.x+1]])    //sasiad po prawej
        {
            wsp s; s.x=v.x+1; s.y=v.y;
            odleglosc[s.y][s.x]=odleglosc[v.y][v.x]+1;
            kolejka.push(s);
        }
        if (v.x-1>0 && !odwiedzony[G[v.y][v.x-1]])    //po lewej
        {
            wsp s; s.x=v.x-1; s.y=v.y;
            odleglosc[s.y][s.x]=odleglosc[v.y][v.x]+1;
            kolejka.push(s);
        }
        if (v.y+1<=N && !odwiedzony[G[v.y+1][v.x]])    //na gorze
        {
            wsp s; s.x=v.x; s.y=v.y+1;
            odleglosc[s.y][s.x]=odleglosc[v.y][v.x]+1;
            kolejka.push(s);
        }
        if (v.y-1>0 && !odwiedzony[G[v.y-1][v.x]])    //na dole
        {
            wsp s; s.x=v.x; s.y=v.y-1;
            odleglosc[s.y][s.x]=odleglosc[v.y][v.x]+1;
            kolejka.push(s);
        }
    }
}

Jeśli coś nie działa, to uznajcie, że zrobiłem to specjalnie, żebyście się namęczyli ^^ ale tak szczerze, to starałem się, żeby było OK