Struktura dat grafu a Algorithms (Příklad)
Sarah Chen
Co je to graf v datové struktuře?
Graf je nelineární datová struktura, která se skládá z vrcholů a hran, kde vrcholy obsahují informace nebo data a hrany fungují jako spojnice mezi páry vrcholů.
Používá se k řešení skutečných slovních úloh, jako je nalezení nejlepší trasy do cílového místa a trasy pro telekomunikace a sociální sítě. Uživatelé jsou považováni za uzel v grafu a dráty jsou hrany spojující uživatele.
Pokud jsou hrany reprezentovány jako E a vrcholy jsou reprezentovány jako V, pak lze graf G zapsat jako množinu vrcholů a hran, jako např. G (V, E)
Příklad grafu v datové struktuře
Zde je jednoduchý příklad struktury dat grafu:
Je to jednoduchý neorientovaný graf (jeden druh grafu). Zde je množina vrcholu: {A, B, C,D,E,F}. Dva vrcholy tvoří hranu. Například A a B jsou spojeny hranou. A a F však nejsou spojeny s žádnými hranami.
Terminologie grafů v datové struktuře
Níže jsou uvedeny některé důležité termíny používané ve struktuře dat grafu:
| Období | Description |
|---|---|
| Vrchol | Všechny datové prvky se nazývají vrchol nebo uzel. Na obrázku nahoře jsou A, B, C, D a E vrcholy. |
| Hrana (oblouk) | Spojnice mezi dvěma uzly nebo vrcholy se nazývají hrana (Arc). Má dva konce a je reprezentován jako (startingVertex, endingVertex). |
| Neorientovaný okraj | Je to obousměrná hrana. |
| Režie Edge | Je to jednosměrná hrana. |
| Zatížená hrana | Hrana s hodnotou. |
| Stupeň | V Graphu se počet hran spojených s vrcholem nazývá stupeň. |
| Indegree | Celkový počet příchozích hran připojených k vrcholu. |
| Outdegree | Celkový počet odchozích hran připojených k vrcholu. |
| Vlastní smyčka | Hrana se nazývá vlastní smyčka, pokud se její dva koncové body shodují. |
| Sousedství | Říká se, že vrcholy sousedí, pokud je připojena hrana. |
Typy grafů v datové struktuře
Zde je seznam těch nejběžnějších typy grafů v datové struktuře:
- Režírovaný graf
- Neorientovaný graf
- Vážený graf
- Obousměrný graf
- Nekonečný graf
- Null Graph
- Triviální graf
- Více grafů
- Kompletní graf
- Připojený graf
- Cyklický graf
- Řízený acyklický graf (DAG)
- Graf cyklu
- Bipartitní graf
- Eulerův graf
- Hamiltonův graf
Aplikace grafové datové struktury
Graf má mnoho případů použití. Existuje mnoho algoritmů, které hodně využívají grafy. Zde jsou některé z aplikací grafu:
- Mapy Google používají grafy k nalezení křižovatky dvou silnic a výpočtu vzdálenosti mezi dvěma místy.
Například, Dijkstra, pro nalezení nejkratší vzdálenosti mezi zdrojovým a cílovým místem. - Facebook používá Graphs k nalezení společného přítele uživatelů. Jeho algoritmus považuje každého uživatele za uzel grafu.
- Pro alokaci zdrojů se používá DAG (Direct Acyclic Graph). Kontroluje závislost zdrojů.
- Vyhledávač Google používá k vytvoření hodnocení webových stránek grafy.
- Mapovací zařízení používá grafovou datovou strukturu.
- router a protokol t používá graf, aby zjistil cestu cílové cesty.
