Seznam sousedství a maticová reprezentace grafu
Sarah Chen
⚡ Chytré shrnutí
Seznam sousedství a maticová reprezentace grafu ukládají vrcholy a hrany do paměti, což umožňuje algoritmům procházet sítěmi. Seznam sousedství používá propojené seznamy na vrchol, zatímco matice sousedství používá čtvercovou dvourozměrnou mřížku.
I když vypadají jinak, všechny typy grafů lze reprezentovat podobným způsobem. Obecně existují dva typy grafové reprezentace:
- Matice sousedství
- Seznam sousedů
Seznam sousedů
Seznam sousedních bodů se skládá z propojených seznamů. Každý vrchol je považován za index pole a každý prvek představuje propojený seznam. Tyto propojené seznamy obsahují vrcholy, které sdílejí hranu s indexovým vrcholem.
Zde je příklad seznamu sousedství:
Nechť graf obsahuje V vrcholů a E hran. Prostorová složitost seznamu sousedností je O(V + E), který se škáluje s počtem reálných hran, nikoli s každým možným párem vrcholů.
V nejhorším případě se prostorová složitost stává O(V²) pokud je daný graf úplný graf, protože každý vrchol se pak napojuje na každý další vrchol.
Matice sousedství
Matice sousednosti se skládá z 2D pole. Pro graf s V vrcholy bude velikost matice V × V.
Říci matrix[i][j] = 5To znamená, že mezi uzlem i a uzlem j existuje hrana, kde je váha 5.
Podívejme se na následující graf a jeho matici sousednosti:
Postavili jsme 2D pole pomocí těchto kroků:
Krok 1) Vrchol A má přímou hranu s vrcholem B a váha je 5. Buňka v řádku A a sloupci B bude tedy vyplněna číslem 5. Zbytek buněk v řádku A bude vyplněn nulou.
Krok 2) Vrchol B má přímou hranu s vrcholem C a váha je 4. Buňka v řádku B a sloupci C bude tedy vyplněna 4. Zbývající buňky v řádku B budou vyplněny nulou, protože B nemá žádnou odchozí hranu k žádnému jinému uzlu.
Krok 3) Vrchol C nemá žádné přímé hrany s žádnými jinými vrcholy. Řádek C tedy bude vyplněn nulami.
Krok 4) Vrchol D má orientovanou hranu s A a C.
- Buňka v řádku D a sloupci A bude mít hodnotu 7. Buňka v řádku D a sloupci C bude mít hodnotu 2.
- Zbytek buněk v řádku D bude vyplněn nulami.
Krok 5) Vrchol E má orientovanou hranu s B a D. Buňka v řádku E a sloupci B bude mít hodnotu 6. Buňka v řádku E a sloupci D bude mít hodnotu 3. Zbytek buněk v řádku E bude vyplněn nulami.
Zde je několik bodů, kterých si musíte všimnout:
- Graf nemá žádné vlastní smyčky, když je primární diagonála matice sousednosti rovna 0.
- Graf je orientovaný, pokud buňky v bodech (a, b) a (b, a) neobsahují stejnou hodnotu. Jinak je graf neorientovaný.
- Graf je vážený, pokud je hodnota jakékoli buňky větší než 1.
Hlavním problémem matice sousednosti je, že vyžaduje druhou mocninu prostoru. I hrany, které neexistují, stále alokují buňky v paměti.
Například pokud máme graf se 100 uzly, pak je pro jeho uložení potřeba 10 000 buněk. RAMS menším počtem hran v grafu může být alokace tak velké paměti nehospodárná. Prostorová složitost s využitím matice sousednosti je tedy O(N²), kde N je počet uzlů v grafu.
Seznam sousedství vs. matice sousedství
Před výběrem reprezentace je užitečné porovnat oba modely vedle sebe napříč operacemi, které dominují v reálných grafových úlohách:
| Operavání | Matice sousedství | Seznam sousedů |
|---|---|---|
| Prostorová složitost | O(V²) | O(V + E) |
| Přidat vrchol | O(V²) | O (1) |
| Přidat hranu | O (1) | O (1) |
| Odstranění hrany | O (1) | O(E) |
| Zkontrolovat, zda hrana (i, j) existuje | O (1) | O (stupeň i) |
| Iterujte přes sousedy i | O(V) | O (stupeň i) |
| Nejlepší pro | Husté grafy, časté dotazy na hrany | Řídké grafy, úlohy s vysokou mírou procházení |
Stručně řečeno, matice sousednosti vítězí při vyhledávání hran v konstantním čase, zatímco seznam sousednosti vítězí v iteraci paměti a sousedů, a proto se algoritmy jako BFS, DFS a Dijkstra obvykle párují se seznamy sousednosti.
Výhody a nevýhody grafové reprezentace
Každá reprezentace má své vlastní nevýhody. Znalost silných a slabých stránek obou modelů vám pomůže vybrat ten správný pro problém, který řešíte.
Výhody matice sousednosti:
- Dotazy na existenci hran mezi libovolnou dvojicí vrcholů v konstantním čase O(1).
- Fixní indexování usnadňuje implementaci maticových algoritmů, jako je Floyd-Warshall a tranzitivní uzávěr.
- Vážené hrany se přirozeně vejdou do jedné buňky matice.
Nevýhody matice sousednosti:
- Pokud je graf řídký, plýtvá se pamětí O(V²).
- Přidání nového vrcholu vyžaduje změnu velikosti celé matice.
- Iterování přes sousedy jednoho vrcholu trvá O(V), i když má vrchol jen několik hran.
Výhody seznamu sousedství:
- Používá pouze O(V + E) paměti, což se blíží skutečnému počtu hran v řídkých grafech.
- Přidání nového vrcholu nebo hrany je O(1).
- Traverzální algoritmy jako BFS a DFS iterují sousedy v O(stupni), což dává celkovou dobu běhu O(V + E).
Nevýhody seznamu sousedství:
- Kontrola, zda existuje specifická hrana, trvá O(stupeň) místo O(1).
- Lokalita mezipaměti je slabší, protože propojené seznamy jsou rozptýleny po paměti.
- Vážené hrany potřebují doprovodné pole nebo seznam párů, což mírně komplikuje datovou strukturu.
Kdy použít seznam sousedností vs. matici sousedností
Volba reprezentace závisí na hustotě grafu a operacích, které nejčastěji provádíte. Pro výběr správné struktury použijte tohoto rychlého průvodce:
- Preferujte matici sousednosti když je graf hustý (E je blízké V²), když se hrany zřídka mění a když se váš algoritmus mnohokrát ptá „existuje hrana mezi i a j?“.
- Preferovat seznam sousedství když je graf řídký (E je mnohem menší než V²), když množina vrcholů nebo hran roste během provádění a když procházíte grafem pomocí BFS, DFS nebo Dijkstrův algoritmus pro nalezení nejkratší cesty.
- Preferujte smíšený model (seznam sousedností plus hašovací sada hran), když potřebujete jak rychlou iteraci sousedů, tak i dotazy na hrany O(1), za cenu dodatečné paměti.
Moderní knihovny grafů, jako jsou NetworkX a igraph, standardně používají seznamy sousedností, protože většina reálných grafů – sociální sítě, mapy silnic, webové stránky, závislosti balíčků – je řídká a vyžaduje velké množství procházení.
