Czym jest graf w programowaniu: węzły, krawędzie i przykłady w Pythonie

Lista pamięta kolejność, drzewo pamięta hierarchię. A jak zapisać mapę połączeń między miastami, znajomych w serwisie społecznościowym albo zależności między krokami programu? Tu żadna z tych struktur nie wystarczy, bo każdy element może być połączony z dowolnym innym. Do takich danych służy graf.

To tekst wprowadzający do cyklu o LangGraph, w którym zbudujemy program pseudonimizujący dane wrażliwe. LangGraph zakłada, że rozumiesz, czym są węzły i krawędzie, więc zaczynamy od podstaw, bez żadnych bibliotek zewnętrznych.

Czym jest graf w programowaniu?

Graf składa się z dwóch rzeczy:

To wszystko. Grafem jest więc zarówno mapa dróg, jak i lista „kto kogo obserwuje” oraz plan kroków w programie. Różnicę robi sposób, w jaki łączą się węzły.

Czym różni się graf skierowany od nieskierowanego?

W grafie nieskierowanym krawędź działa w obie strony: jeśli z Warszawy jedzie się do Łodzi, to z Łodzi jedzie się do Warszawy. W grafie skierowanym krawędź ma kierunek: krok „pobierz” poprzedza „sprawdź”, ale nie odwrotnie.

W kolejnych częściach cyklu będziemy pracować na grafie skierowanym, bo program wykonuje kroki w określonym porządku.

Jak zapisać graf w Pythonie?

Najczęstszy sposób to lista sąsiedztwa: słownik, w którym klucz to węzeł, a wartość to lista węzłów, do których z niego dojdziesz. Oto graf dróg między pięcioma miastami (nieskierowany, więc każda droga występuje w obu kierunkach):

# graf nieskierowany: połączenia między miastami
roads = {
    "Warszawa": ["Łódź", "Lublin"],
    "Łódź": ["Warszawa", "Wrocław"],
    "Lublin": ["Warszawa", "Rzeszów"],
    "Wrocław": ["Łódź"],
    "Rzeszów": ["Lublin"],
}

Alternatywą jest macierz sąsiedztwa, czyli tabela wartości „czy są połączone”. Przy grafach, w których większość węzłów nie jest ze sobą połączona (a tak jest w prawie każdym praktycznym przypadku), słownik list zajmuje mniej miejsca i jest czytelniejszy, więc zostajemy przy nim.

Jak przeszukać graf wszerz i znaleźć najkrótszą drogę?

Przeszukiwanie wszerz (BFS) odwiedza najpierw wszystkich sąsiadów węzła startowego, potem sąsiadów sąsiadów i tak dalej. Dzięki temu pierwsza znaleziona droga do celu ma najmniej krawędzi. Potrzebna jest kolejka (deque) i zbiór odwiedzonych węzłów, żeby nie krążyć w kółko:

from collections import deque


def shortest_path(graph: dict[str, list[str]], start: str, goal: str) -> list[str] | None:
    queue = deque([[start]])
    visited = {start}
    while queue:
        path = queue.popleft()
        node = path[-1]
        if node == goal:
            return path
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(path + [neighbour])
    return None

Wynik dla naszej mapy:

shortest_path(roads, "Wrocław", "Rzeszów")
['Wrocław', 'Łódź', 'Warszawa', 'Lublin', 'Rzeszów']

Gdy start i cel są tym samym miastem, funkcja zwraca ['Warszawa'], a gdy w grafie nie ma drogi, zwraca None. Zbiór visited jest tu kluczowy: bez niego pętla w grafie (Warszawa → Łódź → Warszawa → …) nigdy by się nie skończyła.

Jak przeszukać graf w głąb i sprawdzić, co jest osiągalne?

Przeszukiwanie w głąb (DFS) idzie jedną ścieżką tak daleko, jak się da, i dopiero potem wraca. Dobrze nadaje się do pytania „do których węzłów w ogóle da się dojść?”:

def reachable(graph: dict[str, list[str]], start: str) -> set[str]:
    seen: set[str] = set()

    def visit(node: str) -> None:
        if node in seen:
            return
        seen.add(node)
        for neighbour in graph[node]:
            visit(neighbour)

    visit(start)
    return seen

Dla Łodzi dostajemy wszystkie pięć miast: ['Lublin', 'Rzeszów', 'Warszawa', 'Wrocław', 'Łódź']. Obie metody odwiedzają każdy węzeł i każdą krawędź co najwyżej raz, więc dla zwykłych danych są szybkie. Różnią się kolejnością odwiedzin, a więc tym, do czego się nadają: BFS do najkrótszej drogi, DFS do pytań o osiągalność i o cykle.

Czym jest cykl w grafie i jak go wykryć?

Cykl to droga, która wraca do węzła, z którego wyszła. W grafie dróg to normalne (Warszawa → Łódź → Warszawa), ale w grafie kroków programu oznacza kłopot: krok A czeka na B, a B czeka na A. Graf skierowany bez cykli nazywa się acyklicznym.

Cykl wykrywamy przeszukaniem w głąb, zapamiętując, które węzły są właśnie „w trakcie” odwiedzania. Jeśli trafimy na taki węzeł ponownie, znaleźliśmy pętlę:

# graf skierowany: zależności między krokami
steps = {
    "pobierz": ["sprawdź"],
    "sprawdź": ["zapisz", "wyślij"],
    "zapisz": ["wyślij"],
    "wyślij": [],
}


def has_cycle(graph: dict[str, list[str]]) -> bool:
    state: dict[str, str] = {}  # brak wpisu = nieodwiedzony, "in" = w trakcie, "done" = zakończony

    def visit(node: str) -> bool:
        if state.get(node) == "in":
            return True
        if state.get(node) == "done":
            return False
        state[node] = "in"
        if any(visit(n) for n in graph[node]):
            return True
        state[node] = "done"
        return False

    return any(visit(node) for node in graph)

Wynik: has_cycle(steps) zwraca False, a has_cycle({"a": ["b"], "b": ["a"]}) zwraca True. W LangGraph cykle nie są błędem: pozwalają agentowi powtarzać krok, aż warunek się spełni. Ważne, żebyś robił to świadomie i zawsze miał warunek wyjścia.

Czym jest graf stanowy i co to ma wspólnego z LangGraph?

Dotąd węzły były tylko nazwami. Graf stanowy dodaje jedną rzecz: wspólną informację, którą kolejne węzły czytają i zmieniają. Poniżej najprostsza wersja, czyli „wykonawca”, który idzie po grafie kroków i zapisuje w stanie, co odwiedził:

def run(graph: dict[str, list[str]], start: str, state: dict) -> dict:
    node = start
    while node:
        state["log"].append(node)
        node = graph[node][0] if graph[node] else None
    return state

run(steps, "pobierz", {"log": []})
{'log': ['pobierz', 'sprawdź', 'zapisz', 'wyślij']}

To uproszczenie: wykonawca idzie zawsze pierwszą krawędzią, więc nie obsługuje gałęzi ani równoległych kroków. Właśnie te brakujące elementy, czyli wybór krawędzi na podstawie stanu, kroki równoległe, zapis stanu i wznawianie, robi za Ciebie LangGraph. W następnej części cyklu zobaczysz je na działającym przykładzie.

Kiedy graf jest właściwym wyborem, a kiedy wystarczy lista lub drzewo?

Drzewo jest szczególnym przypadkiem grafu (skierowanym, bez cykli, z jednym rodzicem), więc wszystko, czego nauczyłeś się o grafach, działa też na drzewach.

Jak przetestować funkcje na grafach w pytest?

Funkcje na grafach są czyste (nie zmieniają danych wejściowych), więc testuje się je łatwo, na małych grafach zbudowanych ręcznie:

from graphs import has_cycle, reachable, roads, shortest_path, steps


def test_shortest_path_between_distant_cities():
    assert shortest_path(roads, "Wrocław", "Rzeszów") == ["Wrocław", "Łódź", "Warszawa", "Lublin", "Rzeszów"]


def test_shortest_path_to_itself():
    assert shortest_path(roads, "Warszawa", "Warszawa") == ["Warszawa"]


def test_no_path_in_disconnected_graph():
    assert shortest_path({"a": [], "b": []}, "a", "b") is None


def test_reachable_covers_connected_graph():
    assert reachable(roads, "Łódź") == set(roads)


def test_steps_have_no_cycle():
    assert not has_cycle(steps)


def test_cycle_is_detected():
    assert has_cycle({"a": ["b"], "b": ["a"]})

Dwa testy brzegowe (start równy celowi i graf bez połączeń) łapią najczęstsze błędy przy przeszukiwaniu grafów. Podobne podejście do testów opisujemy w artykule o testowaniu kodu z API LLM w pytest.

Jak zacząć pracę z grafem, żeby się nie pomylić?

Zanim napiszesz słownik sąsiedztwa, narysuj węzły i strzałki na kartce. Większość błędów w grafach to nie błędy algorytmu, tylko brakująca albo źle skierowana krawędź, a na rysunku widać ją od razu. Dopiero gdy rysunek się zgadza, przepisz go na kod.

Co dalej?

Znasz już węzły, krawędzie, kierunek, cykle i stan. W następnej części zbudujemy pierwszy graf w LangGraph z gotowym stanem, węzłami i krawędziami warunkowymi. Całą ścieżkę nauki Pythona znajdziesz na stronie ścieżki rozwoju w Pythonie.