Co jsou grafy v počítačové vědě a jaké jsou použití pro? Laicky řečeno nejlépe.
Přečetl jsem si definici na Wikipedii :
Ve výpočetní technice je graf abstraktním datovým typem, který je určen k implementaci konceptů grafů a hypergrafů z matematiky.
Datová struktura grafu se skládá z konečného (a případně proměnného) ) sada uspořádaných párů, nazývaných hrany nebo oblouky, určitých entit nazývaných uzly nebo vrcholy. Stejně jako v matematice se říká, že hrana (x, y) ukazuje nebo přechází z x do y. Uzly mohou být součástí struktury grafu , nebo to mohou být externí entity reprezentované celočíselnými indexy nebo odkazy.
ale já hledám méně formální a srozumitelnější definici.
Komentáře
- Máte na mysli grafy datové struktury?
- Ano, omlouvám se. Zde popsané grafy en.wikipedia.org/wiki/Graph_(abstract_data_type) , jen ‚ m hledám méně formální a srozumitelnější definice.
- @ Justin984 Wikipedia odkazuje na závorky (a je jich tolik),
nepracují, závorky neplatí ‚ nehraje se dobře s formátem Markdown pro odkazy. Nyní pro budoucí potřebu přidejte k vaší otázce vysvětlení v samotné otázce, nikoli v komentářích, nejsou ‚ viditelné a ‚ div je snadné je přehlédnout. ‚ Upravím váš výše uvedený komentář v otázce …
Odpovědět
Dokonalým laickým příkladem může být Facebook . Síť vás, vašich přátel a jejich přátelé atd., jsou souhrnně označováni jako sociální graf .
V tomto „grafu“ jsou lidé považováni za uzly grafu a
hrany jsou odkazy přátelství .
Na Facebooku je přítel obousměrný vztah (A je B „s Friend => B je A“ s), takže graf je Neurčený graf . Síť jako Google+ nebo Twitter by byla považována za Directed Graph , protože zde má vztah vztah.
Všechny tyto grafy jsou označovány jako cyklické grafy, protože vztahy mezi uzly mohou tvořit cykly . Family Tree je na druhé straně speciální druh grafu, který mimo jiné je Acyclic protože v relatioshipu rodokmenů nemohou existovat cykly. (Odborně se tomu říká Directy Acyclic Graph (DAG) , protože je jak režijní, tak acyklický)
To by mělo pokrývat všechny základní žargony zahrnující grafy, takže nyní byste měli být schopni sledovat zbytek materiálu v terénu.
Komentáře
- Nemůže ‚ uvěřit, že tomu tak nebylo ‚ nenapadá mě, že ‚ s nazval facebook graph api. Dobrý příklad!
- Rodokmen není cyklický? Nemělo by to být ‚, ale bohužel to je …
- @MarjanVenema, rodokmen je cyklický ? (Je to ‚ sací graf, takže směr je důležitý při určování cyklů a pravděpodobně krokové vztahy nejsou ‚ Opravdu se to nepočítá.)
- @dbaupp: Nechci zde zacházet do podrobností, takže ‚ zmíním jen jednu word: incest.
- @MarjanVenema, chybíš mi ‚.Cyklus v řízeném grafu je vzor jako
A -> B -> C -> A(tj. Kruh šipek), incest dává pouzeA -> B -> CaA -> D -> C(tj. Diamant). Cyklus v rodokmenu vyžaduje cestování v čase.
Odpověď
Grafy jsou jedním z nejdůležitějších matematických konceptů používá se v informatice.
Grafy jste viděli mnohokrát. Představte si, že letíte letadlem z jednoho města do druhého. Na sedadle nevyhnutelně najdete pěkný lesklý časopis od letecké společnosti. kapsa před vámi. V zadní části tohoto časopisu téměř vždy najdete mapu, která zobrazuje města obsluhovaná leteckou společností představovaná jako kruhy, přičemž lety spojující tato města představují zakřivené čáry. To je graf! Města, reprezentovaná jako kruhy, jsou uzly tohoto grafu a lety, reprezentované jako zakřivené čáry, jsou hrany. Grafy jsou jen věci s uzly a hranami, které spojují uzly.
Tyto jednoduché grafy můžete ozdobit různými způsoby. Když se na tuto mapu díváte, nechcete vidět jen spoustu kruhů a čar. Tato města mají názvy. Výsledkem označení těchto měst je označený graf. (Můžete také označit hrany, např. let 1234.) Počítačová věda často spojuje data s uzly, někdy s hranami, ale to je jen rozšíření štítku. Je to stále označený graf. Další ozdoba je výsledkem, pokud můžete létat přímo z města A do města B, ale ne z města B do města A. Zjevným způsobem, jak to vykreslit, je umístit šipku na čáru, která spojuje města k zobrazení tohoto jednosměrného vztahu. Nyní máte orientovaný graf.
Propojené seznamy, stromy, diagramy přechodu stavu a spousta dalších datových struktur informatiky jsou příklady grafů. Je to velmi silný koncept.
Komentáře
- I ‚ d tento příklad ve skutečnosti rozšířím o to, že všechny entity popsané ve vašem příkladu lze znázornit jako vrcholy v grafu (město, letadlo, časopis, mapa atd.), přičemž samotná mapa je jediným vrcholem.
Odpověď
Lepší otázkou by bylo „K čemu se grafy nepoužívají?“. Počítačová věda je v mnoha ohledech studiem grafů.
Graf, laicky řečeno, je soubor libovolných abstraktních objektů zvaných „uzly“ nebo „vrcholy“, které představují body spojení. Poté jsou spojeny pomocí „cest“ nebo „hran“. Abstraktní datový typ „Graph“ je implementací matematického „Graph“. Takže v zásadě máte uzly a hrany jako pole a různé operace, které na nich můžete provádět. může například přidat nový uzel do kolekce grafu (může to být seznam nebo pole nebo nějaká jiná struktura v závislosti na jazyce). Tento uzel pak můžete propojit se stávajícími uzly. Mezi operace by patřilo také procházení grafem, kontrola, zda dva uzly sdílejí hranu (jsou spojeny), načítání hodnot z uzlů nebo hran a mazání uzlů nebo hran z grafu.
Co se týče využití jde, grafy se používají všude. Síť je obzvláště intenzivně využívá, ale nacházejí se v oblasti umělé inteligence, dolování dat, vývoje her, geoinformatiky a řady dalších oborů. Ve formální informatice vidí ještě větší využití, konkrétně jako způsob reprezentace stavu.
Ve skutečnosti může být cokoli, co můžete reprezentovat jako sadu spojení, reprezentováno jako graf a implementováno prostřednictvím tohoto ADT v některých formulář.
Zde je příklad grafiky, kterou jsem vytvořil:
Odpověď
Graf je jen kolekce objektů spojených čarami zvanými vrcholy.
Termín „graf“ je abstrakcí a zobecněním mnoha datové struktury používané při vývoji softwaru. Propojené seznamy, binární stromy a AST „s jsou všechny grafy.
V zásadě každá kolekce objektů, které má ukazatele, které spojují objekty navzájem, je graf. Jakmile budete mít graf, můžete na něj použít principy teorie grafů a vyřešit určité problémy .