Wikiszótár

szélességi keresés

Magyar

Kiejtés

  • IPA: [ ˈseːlɛʃːeːɡikɛrɛʃeːʃ]

Főnév

szélességi keresés

  1. (matematika, algoritmusok) A BFS (Breadth-First Search) egy gráfkeresési algoritmus, amely a gráf csúcsait szélességi sorrendben járja be. Az algoritmus az adott kiindulópontból indul, majd rétegenként halad, először a közvetlen szomszédokat látogatva meg, mielőtt továbblépne a következő rétegre. Ez az algoritmus különösen hasznos minimális úthosszúságú problémák, például a legkevesebb élből álló út megtalálására egy nem súlyozott gráfban.


Elmélet

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.


Pszeudokód

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)

Python implementáció

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        print(node, end=" ")  # Csúcs feldolgozása
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Példa gráf
graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [1],
    4: [1, 5],
    5: [2, 4]
}

bfs(graph, 0)  # Kimenet: 0 1 2 3 4 5

C++ implementáció

#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[node]) {
            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;
}

Összegzés

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.

Fordítások

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=szélességi_keresés&oldid=3479432”