Seznam sousedství a maticová reprezentace grafu
Sarah Chen
I když vypadají jinak, všechny typy grafů lze reprezentovat podobným způsobem. Obecně existují dva typy reprezentace grafu:
- Matice sousedství
- Seznam sousedů
Seznam sousedů
Adjacency List se skládá z Linked Lists. Každý vrchol je považován za index pole a každý prvek představuje propojený seznam. Tyto propojené seznamy obsahují vrcholy, které mají hrany s vrcholem indexu.
Zde je příklad seznamu sousedství:
Řekněme, že graf obsahuje V počet vrcholů a E počet hran.
Obecně bude složitost prostoru O(V + E).
Nejhorší případ bude složitost prostoru O(V2) pokud je daný graf úplným grafem
Matice sousedství
Adjacency Matrix se skládá z 2D pole. Graf s počtem V vrcholů, velikost matice bude VxV.
Říci, matrix[i][j] = 5. Znamená to, že mezi uzlem i a j je hrana, kde je váha 5.
Podívejme se na následující graf a jeho matici sousedství:
Vytvořili jsme 2D pole pomocí těchto kroků:
Krok 1) Vrchol A má přímou hranu s B a váha je 5. Buňka v řádku A a sloupci B bude tedy vyplněna 5. Zbytek buněk v řádku A bude vyplněn nulou.
Krok 2) Vrcholy B mají přímou hranu s C a váha je 4. Buňka v řádku B a sloupci C tedy bude vyplněna 4. Zbývající buňky v řádku B budou vyplněny nulou, protože B nemá žádnou výstupní hranu. další uzly.
Krok 3) Vrcholy C nemají žádné přímé hrany s žádnými jinými vrcholy. Takže řádek C bude vyplněn nulami.
Krok 4) Vertice D má směrovanou hranu s A a C.
- Zde bude mít buňka v řádku D a sloupci A hodnotu 7. Buňky v řádku D a sloupci C budou mít hodnotu 2.
- Zbytek buněk v řádku D bude vyplněn nulami.
Krok 5) Vrcholy E mají orientovanou hranu s B a D. Buňka v řádku E a sloupci B bude mít hodnotu 6. Buňky v řádku E a sloupci D budou mít hodnotu 3. Zbytek buněk v řádku D 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 sousedství 0.
- Graf je orientovaný graf, pokud indexy (a,b) a (b,a) nemají stejnou hodnotu. Jinak je graf orientovaný graf.
- Graf bude váženým grafem, pokud je hodnota buněk větší než 1.
S maticí sousedství je určitý problém, protože vyžaduje čtvercové mezery. Zde ukládáme hrany, které nejsou spojené. Tyto hrany alokují místo v paměti.
Máme-li například graf se 100 uzly, je potřeba 10 tisíc buněk k jeho uložení do RAM. S menším počtem okrajů v grafu může být alokace tak velké paměti plýtváním. Prostorová složitost pomocí matice sousedství tedy bude O(N2), kde N znamená počet uzlů v grafu.
