Shrnutí na Graf a prohledávání do šířky a do hloubky
Graf a Prohledávání do Šířky a Hloubky (BFS, DFS) – Kompletní Průvodce
Úvod do světa grafů může být fascinující, obzvláště když pochopíme, jakým způsobem jsou tyto složité struktury reprezentovány v počítači. Efektivní reprezentace je klíčová pro výkon algoritmů, které grafy zpracovávají. Tato kapitola vám představí základní způsoby, jak grafy uchovávat v paměti.
Co je to graf?
Graf je fundamentální diskrétní matematická struktura, která slouží k modelování vztahů mezi objekty. Je to mocný nástroj pro reprezentaci nejrůznějších sítí – od sociálních sítí, přes dopravní sítě, až po internet.
Graf G je definován jako uspořádaná dvojice $(V, E)$, kde $V$ je neprázdná konečná množina vrcholů (nebo uzlů) a $E$ je množina hran, které reprezentují spojení mezi vrcholy.
Vrcholy a hrany – základní stavební kameny
- Vrchol (uzel): Představte si ho jako objekt nebo entitu. Může to být město, člověk, webová stránka, nebo cokoli, co chcete modelovat. Jsou to základní prvky, ze kterých je graf složen.
- Hrana: Spojení mezi dvěma vrcholy. Hrany mohou mít různé vlastnosti, které ovlivňují, jak graf modeluje realitu:
- Orientované hrany (digrafy): Mají směr. Představte si jednosměrnou ulici: můžete jet z bodu A do bodu B, ale ne naopak. Značí se šipkou, např. $(u \to v)$.
- Neorientované hrany: Nemají směr. Jako obousměrná silnice nebo přátelství na sociální síti – spojení funguje oběma směry. Značí se čárou, např. $(u - v)$.
- Vážené hrany: Každá hrana má přiřazenou číselnou hodnotu (váhu nebo cenu). Tato hodnota může reprezentovat vzdálenost, čas, náklady nebo kapacitu. Například délka silnice mezi dvěma městy. Grafy bez explicitních vah jsou nevážené grafy a obvykle se předpokládá, že všechny hrany mají váhu 1.
Základní pojmy z teorie grafů
Pro hlubší porozumění grafům je důležité znát několik klíčových pojmů:
- Sousední vrcholy: Dva vrcholy jsou sousední, pokud jsou spojeny hranou. Například v grafu měst jsou dvě města sousední, pokud mezi nimi vede přímá silnice.
- Stupeň vrcholu (neorientovaný graf): Je to počet hran, které jsou incidentní (dotýkají se) s daným vrcholem. Pro orientované grafy rozlišujeme:
- Vstupní stupeň: Počet hran, které vedou do vrcholu.
- Výstupní stupeň: Počet hran, které vedou z vrcholu.
- Cesta: Posloupnost vrcholů, kde je každý vrchol spojen hranou s následujícím vrcholem v posloupnosti. Délka cesty je počet hran v cestě.
- Cyklus: Cesta, která začíná a končí ve stejném vrcholu a žádný jiný vrchol se v ní neopakuje.
- Souvislý graf: Graf, ve kterém existuje cesta mezi každými dvěma vrcholy. Představte si to jako síť silnic, kde se z každého města dostanete do každého jiného města.
Reprezentace grafů v počítači
Pro efektivní práci s grafy v počítači je klíčové vybrat vhodnou datovou strukturu. Existují dva hlavní způsoby, jak grafy reprezentovat:
1. Matice sousednosti
Matice sousednosti je čtvercová matice o rozměrech $V \times V$, kde $V$ je počet vrcholů v grafu. Každý prvek matice $A[i][j]$ indikuje, zda existuje hrana z vrcholu $i$ do vrcholu $j$.
- Pro nevážené grafy: Pokud existuje hrana z $i$ do $j$, pak $A[i][j] = 1$, jinak $A[i][j] = 0$.
- Pro vážené grafy: Pokud existuje hrana z $i$ do $j$, pak $A[i][j]$ obsahuje váhu hrany. Pokud hrana neexistuje, hodnota může být $0$ (pokud váhy nejsou $0$) nebo $\infty$ (reprezentovaná velkým číslem).
Příklad matice sousednosti pro neorientovaný, nevážený graf s 4 vrcholy (0, 1, 2, 3) a hranami (0-1), (0-2), (1-2), (2-3):
$$\begin{pmatrix} 0 & 1 & 1 & 0 \ 1 & 0 & 1 & 0 \ 1 & 1 & 0 & 1 \ 0 & 0 & 1 & 0 \end{pmatrix}$$
Výhody:
- Rychlé zjištění existence hrany: Ověření, zda existuje hrana mezi dvěma vrcholy $u$ a $v$, je otázka konstantního času $O(1)$ (stačí se podívat na p
Zaregistruj se pro celé shrnutíUž máš účet? Přihlásit se
Reprezentace grafů
Klíčová slova: Reprezentace grafů, BFS algoritmus, DFS algoritmus, Algoritmy BFS a DFS
Klíčové pojmy: Graf je matematická struktura $(V, E)$ pro modelování vztahů, kde $V$ jsou vrcholy a $E$ hrany., Vrcholy jsou objekty, hrany jsou spojení, která mohou být orientovaná, neorientovaná nebo vážená., Orientovaná hrana má směr $(u \to v)$, neorientovaná je obousměrná $(u - v)$., Vážené hrany mají přiřazenou číselnou hodnotu (váhu), nevážené mají implicitní váhu 1., Dva vrcholy jsou sousední, pokud jsou spojeny hranou., Stupeň vrcholu je počet incidentních hran; pro orientované grafy se rozlišuje vstupní a výstupní stupeň., Matice sousednosti je $V \times V$ matice, paměť $O(V^2)$, rychlé ověření hran $O(1)$., Seznam sousednosti je pole seznamů, paměť $O(V + E)$, rychlé procházení sousedů $O(\text{stupeň vrcholu})$., Matice sousednosti je vhodná pro husté grafy, seznam sousednosti pro řídké grafy., Výběr reprezentace závisí na vlastnostech grafu (hustý/řídký) a operacích, které se budou provádět.