Se consideră un graf neorientat cu n vârfuri și m muchii și de asemenea un vârf X.

Cerinţa

Să se afișeze vârfurile vizitate în urma parcurgerii în lățime (Breadth First Search) a grafului, pornind din vârful X.

Date de intrare

Fişierul de intrare BFS.in conţine pe prima linie trei numere naturale n m X, având următoarea semnificație: n este numărul de noduri, m este numărul de muchii din graf, iar X este vârful din care se începe parcurgerea. Următoarele m linii conțin câte două numere x y cu semnificația că există muchie între x și y .

Date de ieşire

Fişierul de ieşire BFS.out va conţine pe prima linie vârfurile vizitate în urma parcurgerii în lățime a grafului, aceasta începând din vârful X.

Restricţii şi precizări

2 <= n <= 100
1 <= m <= n*(n-1)/2
Graful poate sa nu fie conex!!!
dacă în timpul parcurgerii, la un moment dat vârful curent al grafului este Y, vecinii nevizitați ai lui Y se vor analiza în ordine crescătoare.

Exemplu

BFS.in

BFS.out

2 1 3 4 5

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema BFS:

#include <fstream>
#include <iostream>
#include <cassert>
using namespace std;
#define NN 500


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

int n, X, a[NN][NN];
char v[NN];
int c[NN];

void citire(){
    int m, q, p ;
    fin >> n >> m >> X;
    assert(X>=1 && X<=n);
    for( ; m ; --m){
        fin >> p >> q;
        assert(p<=n && q<=n);
        a[p][q]= a[q][p] = 1;
    }
}

void BFS(int start){

    int st=1,dr=0;
    v[start]=1;
    c[++dr] = start;
    while(st<=dr){
        int k = c[st];
        for(int i=1;i<=n;++i)
            if(a[k][i]==1 && v[i]==0){
                v[i] = 1;
                c[++dr]=i;
            }
        fout << k << " ";
        st++;
    }
}

int main(){
    citire();
    BFS(X);
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #19 BFS

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #19 BFS de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #19 BFS