Struktura dat grafu

Obsah

Terminologie grafů
Grafové znázornění
Grafické operace

V tomto kurzu se dozvíte, co je datová struktura Graph. Najdete také reprezentace grafu.

Struktura dat grafu je kolekce uzlů, které mají data a jsou připojeny k jiným uzlům.

Zkusme to pochopit na příkladu. Na facebooku je všechno uzel. To zahrnuje uživatele, fotografie, album, událost, skupinu, stránku, komentář, příběh, video, odkaz, poznámku … vše, co má data, je uzel.

Každý vztah je výhodou z jednoho uzlu do druhého. Ať už pošlete fotografii, připojíte se ke skupině, jako je stránka atd., Vytvoří se pro tento vztah nový okraj.

Příklad struktury dat grafu

Celý facebook je pak souborem těchto uzlů a hran. Je to proto, že facebook k ukládání svých dat používá datovou strukturu grafu.

Přesněji řečeno, graf je datová struktura (V, E), kterou tvoří

Sbírka vrcholů V
Kolekce hran E, představovaných jako uspořádané dvojice vrcholů (u, v)

Vrcholy a hrany

V grafu

 V = (0, 1, 2, 3) E = ((0,1), (0,2), (0,3), (1,2)) G = (V, E)

Terminologie grafů

Sousedství : Říká se, že vrchol sousedí s jiným vrcholem, pokud je spojuje hrana. Vrcholy 2 a 3 nesousedí, protože mezi nimi není hrana.
Cesta : Posloupnost hran, která vám umožní přejít z vrcholu A na vrchol B, se nazývá cesta. 0-1, 1-2 a 0-2 jsou cesty od vrcholu 0 k vrcholu 2.
Směrovaný graf : Graf, ve kterém hrana (u, v) nemusí nutně znamenat, že existuje také hrana (v, u). Hrany v takovém grafu jsou znázorněny šipkami, které ukazují směr hrany.

Grafové znázornění

Grafy jsou běžně zobrazovány dvěma způsoby:

1. Matice sousedství

Matice sousedství je 2D pole V x V vrcholů. Každý řádek a sloupec představují vrchol.

Pokud je hodnota libovolného prvku a(i)(j)1, znamená to, že existuje hrana spojující vrchol i a vrchol j.

Matice sousedství pro graf, který jsme vytvořili výše, je

Matice sousedství grafu

Jelikož se jedná o neorientovaný graf, pro hranu (0,2) musíme také označit hranu (2,0); takže matice sousedství je symetrická s úhlopříčkou.

Vyhledávání hran (kontrola, zda hrana existuje mezi vrcholem A a vrcholem B) je extrémně rychlá v reprezentaci sousední matice, ale musíme si vyhradit prostor pro každý možný spoj mezi všemi vrcholy (V x V), takže vyžaduje více prostoru.

2. Seznam sousedů

Seznam sousedství představuje graf jako řadu propojených seznamů.

Index pole představuje vrchol a každý prvek v jeho propojeném seznamu představuje další vrcholy, které tvoří hranu s vrcholem.

Seznam sousedů pro graf, který jsme vytvořili v prvním příkladu, je následující:

Reprezentace seznamu sousedů

Seznam sousedů je efektivní z hlediska úložiště, protože potřebujeme ukládat pouze hodnoty pro hrany. Pro graf s miliony vrcholů to může znamenat spoustu ušetřeného prostoru.