Algoritmul Breadth-First

Căutarea în lăţime

În teoria grafurilor, breadth-first search (BFS) este un algoritm de căutare în grafuri, care începe cu vârful rădăcină şi explorează toate nodurile vecine. Apoi, pentru fiecare dintre aceste noduri se explorează nodurile vecine încă necercetate, ş.a.m.d.., până când scopul a fost atins.
BFS este o metodă de căutare, care ţinteşte extinderea şi examinarea tuturor nodurilor unui graf, cu scopul de a găsi soluţia. Din punct de vedere al algoritmului, toate nodurile „fii” obţinute prin expansiunea unui nod sunt adăugate într-o „coadă” de tipul FIFO (First In First Out). În implementările tipice, nodurile care nu au fost încă examinate de către vecinii corespunzători sunt plasate într-un „recipient” (asemănător unei cozi sau unei liste de legătură), numit „deschis”, iar odată examinaţi sunt plasaţi în „recipientul” „închis”.

Algoritmul

1. Introducerea nodului rădăcină în coadă.
2. Extragerea unui nod din capătul listei şi examinarea acestuia.
􀂙 Dacă elementul căutat se identifică cu acest nod, se renunţă la căutare şi se returnează rezultatul.
􀂙 Altfel, se plasează toţi succesorii (nodurile „fii”) (neexaminaţi încă) acestui nod la sfârşitul „cozii” (acesta în cazul în care există)
3. Dacă „coada” este goală, fiecare nod al grafului a fost examinat – se renunţă la căutare şi se întoarce la „not found”.
4. Repetă începând cu Pasul 2.

Implementare:

Cod Sursa C++

// BreadthFirstCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
 
using namespace std;
 
int a[10][10], c[20], viz[10];
int n, m, prim, ultim, varf;
 
void bf_iterativ() //parcurgerea in latime
{
	int k;
	while (prim <= ultim)
	{
		varf = c[prim];
		for (k = 1; k <= n; k++)
		if (a[varf][k] == 1 && viz[k] == 0) //il adaug pe k in coada daca este vecin pt. varf si nu a fost vizitat
		{
			ultim++;
			c[ultim] = k;
			viz[k] = 1;
		}
		prim++;
	}
}
 
void main()
{
	int x, y;
	/*fstream f; //memorare graf in matrice de adiacenta
	f.open("muchii.txt", ios::in);
	f >> n >> m;*/
	cout << "nr de noduri= ";
	cin >> n;
	cout << "nr de muchii= ";
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		cout << "nod sursa: ";
		cin >> x;
		cout << "nod destinatie: ";
		cin >> y;
		//f >> x >> y;
		a[x][y] = 1;
	}
 
	cout << "matricea de adiac " << endl; // afisare matrice de adiacenta
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
			cout << a[i][j] << " ";
		cout << endl;
	}
 
	int nd;
	prim = ultim = 1;
	cout << "varful de inceput=";
	cin >> nd;  // varful  de la care se porneste parcurgerea
	viz[nd] = 1;
	c[prim] = nd;
	bf_iterativ();
	for (int i = 1; i <= ultim; i++)   //afisarea cozii
		cout << c[i] << " ";
	system("pause");
}

Rezultat: