Úvod do grafu v dátovej štruktúre
Grafy sú nelineárne dátové štruktúry obsahujúce konečnú množinu uzlov a hrán. Uzly sú prvky a hrany sú usporiadané páry spojení medzi uzlami.
Všimnite si slovo nelineárne. Nelineárna dátová štruktúra je taká, kde prvky nie sú usporiadané v sekvenčnom poradí. Napríklad, pole je lineárna dátová štruktúra, pretože prvky sú usporiadané jeden po druhom. Môžete prechádzať všetkými prvkami poľa naraz. To neplatí pre nelineárne dátové štruktúry. Prvky nelineárnej dátovej štruktúry sú usporiadané do viacerých úrovní, často podľa hierarchického vzoru. Grafy sú nelineárne.
Ďalšie slovo, ktoré treba venovať pozornosť, je obmedzené. Definujeme graf tak, aby mal konečný a spočítateľný počet uzlov. Toto je skôr neprijateľný termín. Graf môže mať v podstate nekonečný počet uzlov a stále konečný. Napríklad rodokmeň siahajúci až po Adama a Evu. Toto je relatívne nekonečný graf, je však stále spočítateľný, a preto sa považuje za konečný.
Príklad v reálnom svete
Najlepším príkladom grafov v reálnom svete je Facebook. Každá osoba na Facebooku je uzlom a je pripojená cez okraje. A je priateľom B. B je priateľom C a tak ďalej.
terminológie
Nižšie sú uvedené terminológie grafu v dátovej štruktúre
1. Zobrazenie grafu: Všeobecne je graf reprezentovaný ako dvojica množín (V, E). V je množina vrcholov alebo uzlov. E je skupina hrán. Vo vyššie uvedenom príklade
V = (A, B, C, D, E)
E = (AB, AC, AD, BE, CD, DE)
2. Uzol alebo vrchol: prvky grafu sú spojené hranami.
3. Hrany: Cesta alebo čiara medzi dvoma vrcholmi v grafe.
4. Susedné uzly: Dva uzly sa nazývajú susediace, ak sú spojené hranou. Vo vyššie uvedenom príklade uzol A susedí s uzlami B, C a D, ale nie s uzlom E.
5. Cesta: Cesta je postupnosť hrán medzi dvoma uzlami. Je to v podstate priechod začínajúci sa na jednom uzle a končiaci sa na druhom. Vo vyššie uvedenom príklade existuje viac ciest z uzla A do uzla E.
Cesta (A, E) = (AB, BE)
OR
Cesta (A, E) = (AC, CD, DE)
OR
Cesta (A, E) = (AD, DE)
6. Nepriamy graf: Nepriamy graf je graf, v ktorom hrany nešpecifikujú konkrétny smer. Hrany sú obojsmerné.
príklad
V tomto príklade teda môže byť hrana AC prechádzajúca z A do C a C do A. Podobné ako všetky hrany. Cesta z uzla B do uzla C by bola buď (BA, AC) alebo (BD, DC).
7. Usmernený graf: Usmernený graf je graf, kde sa okraje môžu pohybovať iba v určenom smere.
príklad
V rovnakom príklade sú teraz hrany smerové. Okrajom môžete prechádzať iba v jeho smere. Z uzla B do uzla C teraz neexistuje žiadna cesta.
8. Vážený graf: Vážený graf je graf, pri ktorom sú hrany spojené s hmotnosťou. To je spravidla cena prechodu hranou.
príklad
Teda, v rovnakom príklade, teraz majú okraje s nimi spojenú určitú hmotnosť. Medzi uzlom A a uzlom E. sú dve možné cesty.
Cesta 1 = (AB, BD, DE), Hmotnosť1 = 3 + 2 + 5 = 10
Cesta 2 = (AC, CD, DE), Hmotnosť2 = 1 + 3 + 5 = 9
Jednoznačne by sa dalo prednosť ceste 2, ak je cieľom dosiahnuť uzol E z uzla A s minimálnymi nákladmi.
Základné operácie na grafe
Nižšie sú uvedené základné operácie grafu
1. Pridať alebo odstrániť vrchol
Toto je najjednoduchšia operácia v grafe. Do grafu jednoducho pridáte vrchol. Nemusí byť spojený s iným vrcholom cez okraj. Pri odstraňovaní vrcholu musíte odstrániť všetky hrany, ktoré pochádzajú z ukončeného vrcholu a končia na ňom.
2. Pridať alebo odstrániť okraj
Táto operácia pridá alebo odstráni okraj medzi dvoma vrcholmi. Keď sa odstránia všetky hrany pochádzajúce a končiace na vrchole, vrchol sa stane izolovaným vrcholom.
3. Vyhľadávanie podľa šírky (BFS)
Toto je operácia kríženia v grafe. BFS vodorovne prechádza grafom. To znamená, že prechádza všetkými uzlami na jednej úrovni a potom prejde na ďalšiu úroveň.
Algoritmus BFS začína v hornej časti prvého uzla v grafe a potom k nemu prechádza všetky susedné uzly. Po prejdení všetkých susedných uzlov algoritmus opakuje rovnaký postup pre podriadené uzly.
príklad
Prejdenie vyššie uvedeného grafu spôsobom BFS by bolo výsledkom A -> B -> C -> D -> E -> F -> G. Algoritmus začína od uzla A a prechádza všetkými jeho susednými uzlami B, C a D. Označuje všetky štyri uzly pri návšteve. Len čo prechádzajú všetky susedné uzly A, algoritmus sa presunie k prvému susednému uzlu A a zopakuje rovnaký postup. V tomto prípade je uzlom B a susedné uzly k B sú E a F. Ďalej sa prechádzajú susedné uzly k C. Akonáhle sú všetky uzly navštívené, operácia končí.
4. Hĺbkové prvé vyhľadávanie (DFS)
Hĺbkové prvé vyhľadávanie alebo DFS prechádza grafom vertikálne. Začína koreňovým uzlom alebo prvým uzlom grafu a prechádza všetkými podriadenými uzlami pred presunom do susedných uzlov.
príklad
Prejdenie vyššie uvedeného grafu spôsobom BFS by bolo výsledkom A -> B -> E -> F -> C -> G -> D. Algoritmus začína od uzla A a prechádza všetkými jeho podriadenými uzlami. Akonáhle narazí na B, zdá sa, že má ďalšie podriadené uzly. Takže detské uzly B prejdú predtým, ako prejdeme k nasledujúcemu detskému uzlu A.
Implementácia grafov v reálnom svete
- Návrh elektrických obvodov na prenos energie.
- Návrh siete vzájomne prepojených počítačov.
- Štúdium molekulárnej, chemickej a bunkovej štruktúry akejkoľvek látky, napr. Ľudskej DNA.
- Návrh dopravných trás medzi mestami a miestami v meste.
Záver - graf v dátovej štruktúre
Grafy sú veľmi užitočným konceptom v dátových štruktúrach. Praktické implementácie má takmer vo všetkých oblastiach. Je veľmi dôležité porozumieť základom teórie grafov, porozumieť algoritmom štruktúry grafov.
Tento článok bol iba úvodom do grafov. Je to len odrazový mostík. Odporúča sa hlbšie ponoriť do témy teórie grafov.
Odporúčané články
Toto je sprievodca grafom v dátovej štruktúre. Tu diskutujeme terminológie a základné operácie grafu v dátovej štruktúre. Viac informácií nájdete aj v nasledujúcom článku -
- Otázky týkajúce sa rozhovoru o štruktúre údajov
- Dátový model v Cassandre
- Čo je Data Mart?
- Čo je to vedec údajov?