1. Wstęp: świat połączony jak pajęczyna
Wyobraź sobie, że w twoim mieście mieszkają ludzie, którzy znają się ze sobą. Ty znasz Olę i Kubę, Ola zna ciebie i Marcina, a Marcin zna Olę i Kasię.
Gdybyśmy to narysowali, wyglądałoby to jak pajęczyna: kółka (czyli osoby) połączone liniami (czyli znajomościami).
Taką pajęczynę połączeń w informatyce nazywamy grafem.
Graf to nic innego jak zbiór punktów (wierzchołków) i połączeń między nimi (krawędzi).
2. Czym właściwie jest graf?
Graf to sposób przedstawiania różnych połączeń, zależności lub dróg między elementami.
Każdy element (np. człowiek, miasto, komputer, stacja metra) to wierzchołek.
Każde połączenie między nimi (np. przyjaźń, droga, kabel, tunel) to krawędź.
Można to porównać do:
- mapy dróg – miasta to wierzchołki, drogi między nimi to krawędzie,
- sieci społecznej – ludzie to wierzchołki, znajomości to krawędzie,
- metra – stacje to wierzchołki, tory między stacjami to krawędzie.
3. Rodzaje grafów – czyli jakie mogą być połączenia
a) Graf nieskierowany
To graf, w którym połączenie działa w obie strony.
Jeśli Tomek zna Olę, to znaczy, że Ola zna Tomka – linia nie ma strzałki.
W ten sposób działa większość przyjaźni.
b) Graf skierowany
Tutaj kierunek ma znaczenie.
Na przykład: Tomek obserwuje Olę na Instagramie, ale Ola nie obserwuje Tomka.
Rysujemy strzałkę od Tomka do Oli.
To już graf skierowany, bo relacja nie jest wzajemna.
c) Graf ważony
Czasem połączenia mają swoją „wartość” – np. długość drogi, czas przejazdu, koszt biletu.
Wtedy każda linia ma „wagę”, czyli liczbę oznaczającą koszt, dystans lub czas.
Takie grafy wykorzystuje się np. do planowania tras w metrze, GPS-ach albo grach.
4. Prosty przykład z życia młodego człowieka
Wyobraź sobie, że jesteś ty i twoi znajomi:
Ty znasz Olę i Kubę. Ola zna ciebie i Marcina. Marcin zna Olę i Kasię.
Narysuj to jako kółka połączone liniami.
To jest graf!
Pokazuje, kto kogo zna.
W informatyce komputer może taki graf zapisać w postaci listy:
Ty: Ola, Kuba
Ola: Ty, Marcin
Kuba: Ty
Marcin: Ola, Kasia
Kasia: Marcin
Dzięki temu program może np. policzyć:
- kto ma najwięcej znajomych (najwięcej połączeń),
- przez kogo najłatwiej przejść, by dotrzeć z jednej osoby do drugiej (np. Ty → Ola → Marcin → Kasia),
- kto jest „centrum towarzyskim”.
5. Graf w Pythonie – mała sieć znajomych
# Reprezentacja grafu jako słownika
graf = {
"Ty": ["Ola", "Kuba"],
"Ola": ["Ty", "Marcin"],
"Kuba": ["Ty"],
"Marcin": ["Ola", "Kasia"],
"Kasia": ["Marcin"]
}
# Policz ilu znajomych ma każda osoba
for osoba in graf:
print(f"{osoba} ma {len(graf[osoba])} znajomych: {graf[osoba]}")
# Sprawdź czy Ty możesz dotrzeć do Kasi (czy jest ścieżka)
def znajdz_sciezke(graf, start, cel, odwiedzone=None):
if odwiedzone is None:
odwiedzone = set()
if start == cel:
return [start]
odwiedzone.add(start)
for sasiad in graf[start]:
if sasiad not in odwiedzone:
sciezka = znajdz_sciezke(graf, sasiad, cel, odwiedzone)
if sciezka:
return [start] + sciezka
return None
print("Droga z Ciebie do Kasi:", znajdz_sciezke(graf, "Ty", "Kasia"))
Wynik:
Ty ma 2 znajomych: ['Ola', 'Kuba']
Ola ma 2 znajomych: ['Ty', 'Marcin']
...
Droga z Ciebie do Kasi: ['Ty', 'Ola', 'Marcin', 'Kasia']
6. Graf jako metro w Paryżu
Teraz wyobraź sobie metro w Paryżu.
Każda stacja to wierzchołek, a tor między stacjami to krawędź.
Niektóre stacje są bardzo „popularne”, bo można z nich pojechać w wiele miejsc – np. Châtelet, Concorde czy Bastille.
Możemy to zapisać tak:
metro = {
"Châtelet": ["Les Halles", "Bastille", "Concorde"],
"Les Halles": ["Châtelet", "Bastille"],
"Bastille": ["Châtelet", "Les Halles"],
"Concorde": ["Châtelet"]
}
Program może teraz policzyć:
- ile stacji można odwiedzić z danej stacji (liczba sąsiadów),
- znaleźć najkrótszą trasę z jednej stacji do drugiej (np. z Les Halles do Concorde).
7. Znajdowanie najkrótszej trasy (BFS – prosta wersja)
from collections import deque
def najkrotsza_trasa(graf, start, cel):
kolejka = deque([[start]])
odwiedzone = set()
while kolejka:
sciezka = kolejka.popleft()
stacja = sciezka[-1]
if stacja == cel:
return sciezka
if stacja not in odwiedzone:
odwiedzone.add(stacja)
for sasiad in graf.get(stacja, []):
nowa = list(sciezka)
nowa.append(sasiad)
kolejka.append(nowa)
return None
print("Najkrótsza trasa:", najkrotsza_trasa(metro, "Les Halles", "Concorde"))
Wynik:
Najkrótsza trasa: ['Les Halles', 'Châtelet', 'Concorde']
8. Po co to wszystko?
Grafy pomagają w ogromnej liczbie dziedzin:
- Google Maps – znajduje najkrótszą trasę (graf ważony).
- Facebook / Instagram – sugeruje znajomych (graf społeczny).
- Netflix / Spotify – poleca filmy i piosenki podobne do twoich (graf podobieństw).
- Sztuczna inteligencja i gry – planowanie ruchu postaci, dróg, strategii.
Graf to tak naprawdę sposób, w jaki komputer rozumie powiązania między różnymi elementami świata.