Grafy na Maturze: Algorytmy BFS i DFS - Zrozum i Zaimplementuj (Python i C++)

Zadania z grafami na maturze potrafią wywołać gęsią skórkę, ale to mit, że są one zarezerwowane tylko dla olimpijczyków. Graf to po prostu zbiór punktów (nazywanych wierzchołkami), które są ze sobą połączone liniami (krawędziami). Może to reprezentować sieć miast i dróg, znajomości na Facebooku, czy sieć komputerową.

Na egzaminie maturalnym z informatyki od lat królują dwa fundamentalne algorytmy do poruszania się po tych strukturach: DFS (Przeszukiwanie w głąb) oraz BFS (Przeszukiwanie wszerz). Zanim jednak do nich przejdziemy, musimy wiedzieć, jak "wytłumaczyć" komputerowi, jak wygląda nasz graf.

Jak zapisać graf w kodzie? (Reprezentacja)

Aby algorytm mógł działać, musimy zapisać połączenia w zmiennych. Najbardziej elastycznym i polecanym na maturę sposobem jest tzw. lista sąsiedztwa. Dla każdego wierzchołka przechowujemy po prostu listę (lub wektor) jego sąsiadów.

1. Algorytm DFS (Przeszukiwanie w głąb)

DFS (Depth-First Search) działa dokładnie tak, jakbyś przechodził przez labirynt. Wybierasz jedną ścieżkę i idziesz nią tak daleko, jak to tylko możliwe, aż trafisz w ślepy zaułek. Kiedy nie masz już gdzie iść, cofasz się do ostatniego skrzyżowania i sprawdzasz inne odnogi. Aby nie kręcić się w kółko, musisz zaznaczać kredą (w kodzie: tablica visited), w których pokojach już byłeś.

Najprościej i najczytelniej zaimplementować ten algorytm rekurencyjnie. Dobrą praktyką organizacyjną – ułatwiającą czytanie kodu i unikanie błędów zakresu – jest umieszczanie funkcji pomocniczych, takich jak właśnie kod rekurencyjny DFS, na samej górze pliku, tuż pod importami.

Kod - Python (DFS Rekurencyjny)

# Funkcja wewnętrzna przeniesiona wyżej dla lepszej struktury kodu
def dfs(wierzcholek, graf, odwiedzone):
    # Oznaczamy aktualny wierzchołek jako odwiedzony
    odwiedzone[wierzcholek] = True
    print(f"Odwiedzam: {wierzcholek}")
    
    # Odwiedzamy wszystkich nieodwiedzonych sąsiadów
    for sasiad in graf[wierzcholek]:
        if not odwiedzone[sasiad]:
            dfs(sasiad, graf, odwiedzone)

# --- Główna część programu ---
# Przykładowy graf: 0 połączony z 1 i 2; 1 połączony z 0, 3, 4; itd.
graf = [
    [1, 2],    # Sąsiedzi wierzchołka 0
    [0, 3, 4], # Sąsiedzi wierzchołka 1
    [0, 5],    # Sąsiedzi wierzchołka 2
    [1],       # Sąsiedzi wierzchołka 3
    [1],       # Sąsiedzi wierzchołka 4
    [2]        # Sąsiedzi wierzchołka 5
]

liczba_wierzcholkow = len(graf)
odwiedzone = [False] * liczba_wierzcholkow

print("Uruchamiam DFS:")
dfs(0, graf, odwiedzone) # Zaczynamy od wierzchołka 0

Kod - C++ (DFS Rekurencyjny)

#include <iostream>
#include <vector>
using namespace std;

// Funkcja wewnętrzna zdefiniowana wyżej
void dfs(int wierzcholek, const vector<vector<int>>& graf, vector<bool>& odwiedzone) {
    odwiedzone[wierzcholek] = true;
    cout << "Odwiedzam: " << wierzcholek << endl;
    
    for (int sasiad : graf[wierzcholek]) {
        if (!odwiedzone[sasiad]) {
            dfs(sasiad, graf, odwiedzone);
        }
    }
}

int main() {
    // Lista sąsiedztwa
    vector<vector<int>> graf = {
        {1, 2},    // 0
        {0, 3, 4}, // 1
        {0, 5},    // 2
        {1},       // 3
        {1},       // 4
        {2}        // 5
    };
    
    int n = graf.size();
    vector<bool> odwiedzone(n, false);
    
    cout << "Uruchamiam DFS:" << endl;
    dfs(0, graf, odwiedzone);
    
    return 0;
}

2. Algorytm BFS (Przeszukiwanie wszerz)

BFS (Breadth-First Search) zachowuje się jak kropla wody, która uderza w taflę jeziora i rozchodzi się równomiernie we wszystkich kierunkach. Najpierw sprawdzamy wierzchołek startowy. Potem WSZYSTKICH jego bezpośrednich sąsiadów (odległość 1). Potem wszystkich sąsiadów sąsiadów (odległość 2) i tak dalej. Złożoność obu algorytmów (DFS i BFS) wynosi O(V + E), gdzie V to liczba wierzchołków, a E krawędzi.

Kod - Python (BFS z użyciem kolejki)

from collections import deque

# Wewnętrzna funkcja pomocnicza przeniesiona wyżej
def bfs(start, graf, odwiedzone):
    kolejka = deque()
    
    # Zaczynamy od wierzchołka startowego
    kolejka.append(start)
    odwiedzone[start] = True
    
    while len(kolejka) > 0:
        # Wyciągamy pierwszy element z lewej strony kolejki
        wierzcholek = kolejka.popleft()
        print(f"Odwiedzam: {wierzcholek}")
        
        # Dodajemy do kolejki wszystkich nieodwiedzonych sąsiadów
        for sasiad in graf[wierzcholek]:
            if not odwiedzone[sasiad]:
                odwiedzone[sasiad] = True # Oznaczamy od razu, by nie dodać go dwa razy!
                kolejka.append(sasiad)

# --- Główna część programu ---
graf = [
    [1, 2],
    [0, 3, 4],
    [0, 5],
    [1],
    [1],
    [2]
]

odwiedzone = [False] * len(graf)
print("Uruchamiam BFS:")
bfs(0, graf, odwiedzone)

Kod - C++ (BFS z użyciem queue)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// Funkcja pomocnicza wyżej w hierarchii
void bfs(int start, const vector<vector<int>>& graf, vector<bool>& odwiedzone) {
    queue<int> kolejka;
    
    kolejka.push(start);
    odwiedzone[start] = true;
    
    while (!kolejka.empty()) {
        int wierzcholek = kolejka.front();
        kolejka.pop(); // Usunięcie elementu z przodu kolejki
        
        cout << "Odwiedzam: " << wierzcholek << endl;
        
        for (int sasiad : graf[wierzcholek]) {
            if (!odwiedzone[sasiad]) {
                odwiedzone[sasiad] = true;
                kolejka.push(sasiad);
            }
        }
    }
}

int main() {
    vector<vector<int>> graf = {
        {1, 2}, {0, 3, 4}, {0, 5}, {1}, {1}, {2}
    };
    
    vector<bool> odwiedzone(graf.size(), false);
    
    cout << "Uruchamiam BFS:" << endl;
    bfs(0, graf, odwiedzone);
    
    return 0;
}

Kiedy używać DFS, a kiedy BFS na maturze?

Oba algorytmy mają złożoność liniową w stosunku do wielkości grafu, ale ich charakterystyka pracy określa ich zastosowania w konkretnych zadaniach.

Typowe zadania maturalne z grafów

• "Sprawdź, czy z miasta A można dojechać do miasta B" - Uruchamiasz BFS lub DFS od miasta A. Na końcu sprawdzasz, czy odwiedzone[B] == True.
• "Podziel uczniów na grupy, tak by znajomi byli w jednej grupie (znajdowanie tzw. spójnych składowych)" - W pętli przechodzisz po wszystkich osobach. Jeśli ktoś nie jest odwiedzony, uruchamiasz od niego DFS i przypisujesz odnalezionym nowy numer grupy.
• "Jaka jest najmniejsza liczba przesiadek z punktu X do Y?" - Klasyczny problem BFS. Musisz do algorytmu dołożyć tablicę odleglosc[], którą aktualizujesz: odleglosc[sasiad] = odleglosc[wierzcholek] + 1.

Podsumowanie - na co uważać?

1. Pamiętaj o oznaczaniu jako odwiedzone! Zapomnienie o tablicy visited to najczęstszy błąd, który skutkuje wpadnięciem w nieskończoną pętlę (lub przepełnieniem stosu rekurencji).
2. Oznaczaj od razu przy dodawaniu do kolejki. W BFS ustawiaj odwiedzone[sasiad] = True w momencie push()/append(), a nie dopiero po wyciągnięciu z niej. Zapobiegnie to wkładaniu tego samego elementu wiele razy.
3. Właściwa organizacja kodu. Zawsze definiuj funkcje algorytmów DFS i BFS powyżej miejsca, w którym ich używasz (na górze pliku), aby zachować porządek w logice programu.

Chcesz opanować grafy do perfekcji? Sprawdź nasz kurs do matury z informatyki, gdzie analizujemy arkusze krok po kroku.