A BFS a következőképpen működik: 1. Kezdet: A kiinduló csúcsot bejelöljük látogatottként, és hozzáadjuk egy sorhoz (queue). 2. Ismétlés: Amíg a sor nem üres: - Vegyük ki a sor elején lévő csúcsot. - Az aktuális csúcs összes szomszédját bejárjuk: - Ha egy szomszédot még nem látogattunk meg, jelöljük látogatottként, és adjuk hozzá a sorhoz. 3. Vég: A sor kiürülésekor az algoritmus befejeződik, a gráf összes elérhető csúcsát bejártuk.
Fontos tulajdonságok: - Időkomplexitás: ( O(V + E) ), ahol ( V ) a csúcsok száma, ( E ) pedig az élek száma. - Térkomplexitás: ( O(V) ), a látogatott csúcsok és a sor tárolása miatt.
BFS(G, start):
Látogatott = üres halmaz
Sor = üres sor
Sorba helyez(start)
Jelöld látogatottként(start)
amíg Sor nem üres:
csúcs = Sorból eltávolít()
Feldolgozd(csúcs)
minden szomszéd S a csúcs szomszédai közül:
ha S nincs látogatottként jelölve:
Jelöld látogatottként(S)
Sorba helyez(S)
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque()
visited.add(start)
while queue:
node = queue.popleft()
print(node, end=" ") # Csúcs feldolgozása
for neighbor in graph:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# Példa gráf
graph = {
0: ,
1: ,
2: ,
3: ,
4: ,
5:
}
bfs(graph, 0) # Kimenet: 0 1 2 3 4 5
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
void bfs(const vector<vector<int>>& graph, int start) {
unordered_set<int> visited;
queue<int> q;
visited.insert(start);
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
cout << node << " "; // Csúcs feldolgozása
for (int neighbor : graph) {
if (visited.find(neighbor) == visited.end()) {
visited.insert(neighbor);
q.push(neighbor);
}
}
}
}
int main() {
// Példa gráf
vector<vector<int>> graph = {
{1, 2}, // 0. csúcs szomszédai
{0, 3, 4}, // 1. csúcs szomszédai
{0, 5}, // 2. csúcs szomszédai
{1}, // 3. csúcs szomszédai
{1, 5}, // 4. csúcs szomszédai
{2, 4} // 5. csúcs szomszédai
};
bfs(graph, 0); // Kimenet: 0 1 2 3 4 5
return 0;
}
A BFS egy egyszerű, mégis erőteljes algoritmus, amely a gráfok szélességi bejárására szolgál. Mind Pythonban, mind C++-ban könnyen implementálható, és sokféle feladatra alkalmazható, például legkisebb úthossz keresésére vagy összefüggő komponensek feltárására.