Úvod do grafu ve struktuře dat
Grafy jsou nelineární datové struktury obsahující konečnou sadu uzlů a hran. Uzly jsou prvky a hrany jsou uspořádány páry spojení mezi uzly.
Všimněte si slova nelineární. Nelineární datová struktura je taková, kde prvky nejsou uspořádány v sekvenčním pořadí. Například pole je lineární datová struktura, protože prvky jsou uspořádány jeden po druhém. V jednom běhu můžete procházet všechny prvky pole. To není případ nelineárních datových struktur. Prvky nelineární datové struktury jsou uspořádány do více úrovní, často podle hierarchického vzoru. Grafy jsou nelineární.
Další slovo, které je třeba věnovat pozornost, je omezené. Definujeme graf tak, aby měl konečný a spočitatelný počet uzlů. Toto je poněkud nepřijatelný termín. Graf může mít v podstatě nekonečný počet uzlů a stále může být konečný. Například rodokmen sahající až po Adama a Evu. Toto je relativně nekonečný graf, ale je stále počítatelné, a proto se považuje za konečné.
Příklad ze skutečného světa
Nejlepší příklad grafů v reálném světě je Facebook. Každá osoba na Facebooku je uzlem a je propojena přes okraje. A je přítel B. B je přítel C a tak dále.
Terminologie
Zde jsou uvedeny Terminologie grafu ve struktuře dat níže
1. Zobrazení grafu: Obecně je graf reprezentován jako dvojice sad (V, E). V je množina vrcholů nebo uzlů. E je sada hran. Ve výše uvedeném příkladu
V = (A, B, C, D, E)
E = (AB, AC, AD, BE, CD, DE)
2. Uzel nebo vrchol: Prvky grafu jsou spojeny hranami.
3. Hrany: Cesta nebo čára mezi dvěma vrcholy v grafu.
4. Sousední uzly: Dva uzly se nazývají sousední, pokud jsou spojeny hranou. Ve výše uvedeném příkladu uzel A sousedí s uzly B, C a D, ale ne s uzlem E.
5. Cesta: Cesta je posloupnost hran mezi dvěma uzly. Jde v podstatě o traverzu začínající v jednom uzlu a končící v jiném. Ve výše uvedeném příkladu existuje více cest z uzlu A do uzlu E.
Cesta (A, E) = (AB, BE)
NEBO
Cesta (A, E) = (AC, CD, DE)
NEBO
Cesta (A, E) = (AD, DE)
6. Neřízený graf: Neřízený graf je graf, kde okraje neurčují konkrétní směr. Hrany jsou obousměrné.
Příklad
V tomto příkladu tedy může být hrana AC posouvána z A do C a C do A. Podobně jako u všech hran. Cesta z uzlu B do uzlu C by byla buď (BA, AC) nebo (BD, DC).
7. Řízený graf: Řízený graf je graf, ve kterém lze hrany procházet pouze v určeném směru.
Příklad
Ve stejném příkladu jsou nyní hrany směrové. Okrajem můžete procházet pouze ve směru. Nyní neexistuje žádná cesta z uzlu B do uzlu C.
8. Vážený graf: Vážený graf je graf, kde jsou hrany spojeny s váhou. To je obecně cena za překročení hrany.
Příklad
Tedy, ve stejném příkladu, nyní mají hrany s nimi spojenou určitou váhu. Mezi uzlem A a uzlem E. jsou dvě možné cesty.
Cesta 1 = (AB, BD, DE), Hmotnost1 = 3 + 2 + 5 = 10
Cesta 2 = (AC, CD, DE), Hmotnost2 = 1 + 3 + 5 = 9
Je zřejmé, že by se dalo přednost cestě 2, pokud je cílem dosáhnout uzlu E z uzlu A s minimálními náklady.
Základní operace na grafu
Níže jsou uvedeny základní operace grafu
1. Přidat / odebrat vrchol
Toto je nejjednodušší operace v grafu. Do grafu jednoduše přidáte vrchol. Nemusí to být spojeno s žádným jiným vrcholem přes okraj. Při odstraňování vrcholu musíte odstranit všechny hrany pocházející a končící na odstraněném vrcholu.
2. Přidat nebo odebrat hranu
Tato operace přidá nebo odstraní hranu mezi dvěma vrcholy. Když jsou odstraněny všechny hrany pocházející a končící na vrcholu, vrchol se stává izolovaným vrcholem.
3. Hledání podle šířky (BFS)
V grafu se jedná o pohybovou operaci. BFS vodorovně prochází grafem. To znamená, že projde všechny uzly na jedné úrovni a poté přejde na další úroveň.
Algoritmus BFS začíná v horní části prvního uzlu v grafu a poté k němu prochází všechny sousední uzly. Jakmile jsou procházeny všechny sousední uzly, algoritmus opakuje stejný postup pro podřízené uzly.
Příklad
Procházení výše uvedeného grafu v módě BFS by bylo výsledkem A -> B -> C -> D -> E -> F -> G. Algoritmus začíná od uzlu A a prochází všemi jeho sousedními uzly B, C a D. Označuje všechny čtyři uzly při návštěvě. Jakmile jsou procházeny všechny sousední uzly A, algoritmus se přesune do prvního sousedního uzlu A a opakuje stejný postup. V tomto případě je uzlem B a přilehlé uzly k B jsou E a F. Dále jsou přilehlé uzly k C překročeny. Jakmile jsou všechny uzly navštíveny, operace končí.
4. Hloubkové první vyhledávání (DFS)
Hloubka prvního vyhledávání nebo DFS posouvá graf svisle. Začíná kořenovým uzlem nebo prvním uzlem grafu a prochází všemi podřízenými uzly před přechodem na sousední uzly.
Příklad
Procházení výše uvedeného grafu v módě BFS by bylo výsledkem A -> B -> E -> F -> C -> G -> D. Algoritmus začíná od uzlu A a prochází všemi jeho podřízenými uzly. Jakmile narazí na B, zdá se, že má další podřízené uzly. Podřízené uzly B tedy procházejí před přechodem na další podřízený uzel A.
Real-World implementace grafů
- Návrh elektrických obvodů pro přenos energie.
- Návrh sítě propojených počítačů.
- Studium molekulární, chemické a buněčné struktury jakékoli látky, např. Lidské DNA.
- Návrh dopravních tras mezi městy a místy ve městě.
Závěr - Graf ve struktuře dat
Grafy jsou velmi užitečným konceptem v datových strukturách. Má praktické implementace téměř ve všech oborech. Je velmi důležité porozumět základům teorie grafů, rozvinout porozumění algoritmům struktury grafu.
Tento článek byl pouze úvodem do grafů. Je to jen odrazový můstek. Doporučuje se hlouběji se potápět v tématu teorie grafů.
Doporučené články
Toto je průvodce grafem ve struktuře dat. Zde diskutujeme Terminologie a základní operace grafu ve struktuře dat. Další informace naleznete také v následujícím článku -
- Rozhovory s dotazem na strukturu dat
- Datový model v Cassandře
- Co je Data Mart?
- Co je to datový vědec?