BLOK 07 · 2 godz. Grafy BFS DFS

Grafy: reprezentacja, przechodzenie (BFS/DFS) i zastosowania

Informatyka Rozszerzona · Klasa 4 · Semestr I · Blok 07/30

1. Czym jest graf?

Graf to struktura składająca się z wierzchołków (ang. vertices) połączonych krawędziami (ang. edges). Grafy modelują relacje między obiektami: mapy dróg, sieci społecznościowe, połączenia internetowe, zależności między zadaniami.

Rodzaj grafu	Opis	Przykład
Nieskierowany	Krawędź działa w obie strony	Znajomości na Facebooku
Skierowany (digraf)	Krawędź ma kierunek	Obserwowanie na Twitterze/X
Ważony	Krawędzie mają przypisaną wartość (koszt)	Mapa dróg z odległościami

2. Reprezentacja grafu w programie

Macierz sąsiedztwa

Tablica dwuwymiarowa n×n, gdzie macierz[i][j] = 1 oznacza krawędź między wierzchołkami i oraz j. Zajmuje O(V²) pamięci niezależnie od liczby krawędzi — dobra dla gęstych grafów.

macierz = [
    [0, 1, 1, 0],
    [1, 0, 1, 0],
    [1, 1, 0, 1],
    [0, 0, 1, 0],
]

Lista sąsiedztwa

Słownik, gdzie każdy wierzchołek wskazuje na listę swoich sąsiadów. Zajmuje O(V + E) pamięci — znacznie oszczędniejsza dla grafów rzadkich (typowych w praktyce).

graf = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B', 'D'],
    'D': ['C'],
}

3. Przechodzenie grafu: BFS i DFS

BFS (przeszukiwanie wszerz) — wykorzystuje kolejkę

Odwiedza wierzchołki "warstwami" — najpierw wszystkich sąsiadów, potem sąsiadów sąsiadów. Znajduje najkrótszą ścieżkę pod względem liczby krawędzi w grafie nieskierowanym/nieważonym.

from collections import deque

def bfs(graf, start):
    odwiedzone = {start}
    kolejka = deque([start])
    kolejnosc = []
    while kolejka:
        wierzcholek = kolejka.popleft()
        kolejnosc.append(wierzcholek)
        for sasiad in graf[wierzcholek]:
            if sasiad not in odwiedzone:
                odwiedzone.add(sasiad)
                kolejka.append(sasiad)
    return kolejnosc

DFS (przeszukiwanie w głąb) — wykorzystuje stos (lub rekurencję)

Zagłębia się maksymalnie w jedną ścieżkę, zanim zawróci. Naturalnie implementowana rekurencyjnie (bo rekurencja sama w sobie używa stosu wywołań).

def dfs(graf, wierzcholek, odwiedzone=None):
    if odwiedzone is None:
        odwiedzone = set()
    odwiedzone.add(wierzcholek)
    print(wierzcholek)
    for sasiad in graf[wierzcholek]:
        if sasiad not in odwiedzone:
            dfs(graf, sasiad, odwiedzone)

4. Zastosowania grafów

Nawigacja GPS — miasta jako wierzchołki, drogi jako krawędzie ważone odległością (szukanie najkrótszej drogi — poznamy algorytm zachłanny Dijkstry w Bloku 15).
Sieci społecznościowe — sugestie znajomych to często "znajomi znajomych" znalezieni przez BFS.
Kompilatory — graf zależności między modułami/plikami do ustalenia kolejności kompilacji.
Wyszukiwarki internetowe — sieć stron WWW jako graf skierowany (algorytm PageRank).

5. Ćwiczenia praktyczne

Ćwiczenie 1 — zbadaj spójność grafu

Wykorzystując funkcję bfs, napisz funkcję czy_spojny(graf), która sprawdzi, czy ze startowego wierzchołka można dojść do wszystkich pozostałych (czyli czy graf jest spójny).

def czy_spojny(graf):
    start = next(iter(graf))
    odwiedzone = bfs(graf, start)
    return len(odwiedzone) == len(graf)

Ćwiczenie 2 — najkrótsza liczba krawędzi

Zmodyfikuj BFS, aby oprócz kolejności odwiedzania zwracał także słownik odległości (w liczbie krawędzi) od wierzchołka startowego do każdego innego wierzchołka.

Sprawdź wiedzę

1. Która struktura danych jest naturalnie używana do implementacji BFS?

Kolejka Stos Tablica haszująca

2. Jaka jest złożoność pamięciowa reprezentacji grafu listą sąsiedztwa?

O(V²) O(V + E) O(E²)

3. Który algorytm zagłębia się maksymalnie w jedną ścieżkę przed zawróceniem?

BFS DFS Sortowanie topologiczne

Podsumowanie bloku

Rozumiem różnicę między grafem skierowanym, nieskierowanym i ważonym.
Potrafię zapisać graf jako macierz sąsiedztwa i jako listę sąsiedztwa.
Potrafię zaimplementować BFS i DFS oraz wiem, kiedy stosować który z nich.
Znam co najmniej trzy praktyczne zastosowania grafów w informatyce.

← Blok 06: Algorytmy tekstowe Blok 08: MergeSort →