Bredden-först-sökning (BFS)

Breadth-first search (BFS) undersöker en graf i nivåer utifrån en startnod. Algoritmen använder en FIFO-kö: den nod som upptäcktes först behandlas först. I en oviktad graf, eller där alla kanter har lika kostnad, ger första upptäckten minsta antalet kanter från start om algoritmen samtidigt lagrar avstånd eller föräldrar.

Följ grafen steg för steg

Besökta: –

Queue: –

FöregåendeNästa stegÅterställ

Grannar behandlas i alfabetisk ordning. DFS använder omvänd push-ordning för att besöka den alfabetiskt första grannen först.

Välj BFS och börja vid A. När A behandlats läggs dess grannar i kön. Nästa steg tar bort första elementet, behandlar det och lägger till nya grannar. Visualiseringen visar kön som återstår efter steget. Kanterna är oriktade och grannarna behandlas alfabetiskt.

C# och C++

C#

C# | BFS.cs

using System.Collections.Generic;

static List<int> Bfs(IReadOnlyList<int>[] graph, int start)
{
    if ((uint)start >= (uint)graph.Length)
        throw new ArgumentOutOfRangeException(nameof(start));
    var visited = new bool[graph.Length];
    var queue = new Queue<int>();
    var order = new List<int>();
    visited[start] = true;
    queue.Enqueue(start);
    while (queue.Count > 0)
    {
        int current = queue.Dequeue();
        order.Add(current);
        foreach (int next in graph[current])
        {
            if ((uint)next >= (uint)graph.Length)
                throw new ArgumentException("Invalid neighbor index", nameof(graph));
            if (visited[next]) continue;
            visited[next] = true;
            queue.Enqueue(next);
        }
    }
    return order;
}

C++

C++ | BFS.cpp

#include <vector>
#include <queue>
#include <stdexcept>

std::vector<int> bfs(const std::vector<std::vector<int>>& graph, int start) {
    if (start < 0 || static_cast<std::size_t>(start) >= graph.size())
        throw std::out_of_range("start");
    std::vector<bool> visited(graph.size(), false);
    std::queue<int> queue;
    std::vector<int> order;
    visited[start] = true;
    queue.push(start);
    while (!queue.empty()) {
        int current = queue.front(); queue.pop();
        order.push_back(current);
        for (int next : graph[current]) {
            if (next < 0 || static_cast<std::size_t>(next) >= graph.size())
                throw std::out_of_range("neighbor");
            if (visited[next]) continue;
            visited[next] = true;
            queue.push(next);
        }
    }
    return order;
}

Koden returnerar besöksordningen, inte kortaste vägar. För att bygga en väg sparar du parent[next] = current vid första upptäckten och följer sedan kedjan bakåt. För att beräkna avstånd i antal kanter anger du distance[start] = 0 och sätter avståndet till nya grannar till distance[current] + 1.

Varför markera vid enqueue?

Om du markerar först vid dequeue kan samma nod läggas in flera gånger av olika grannar. Det ger onödigt köminne och extra arbete. Markera därför när noden upptäcks. Grannindex bör valideras före arrayindexering; exemplen kastar undantag för ogiltiga index och förutsätter att grafen är rimligt formad.

Komplexitet och begränsningar

För grannlistor kräver BFS O(V + E) tid för den nåbara delen. Om alla separata komponenter gås igenom blir totalen O(V + E). Visited-array och kö använder O(V) extraminne, och resultatlistan tar också O(V) lagring. En grannmatris kan kräva O(V²) vid en full genomgång.

BFS hittar inte vägen med lägst total vikt när kanter har olika kostnader. Där behövs till exempel Dijkstra. DFS garanterar inte heller kortaste väg i en oviktad graf.

Övning

Förutsäg kön efter A och följ stegen. Rita en isolerad nod: varför kan BFS från A inte nå den? Hur skulle du besöka alla komponenter?

Referenser: Codecademy BFS, W3Schools graftraversering, Wikipedia BFS.