logo

TechCodeview

Graf Data Struktura A Algoritmy

Struktura dat grafu je sbírka uzly připojeno pomocí okraje . Používá se k reprezentaci vztahů mezi různými entitami. Grafové algoritmy jsou metody používané k manipulaci a analýze grafů, řešení různých problémů jako najít nejkratší cestu nebo detekční cykly.

js víceřádkový řetězec



Obsah

Komponenty grafu:

  • Vrcholy: Vrcholy jsou základní jednotky grafu. Někdy jsou vrcholy také známé jako vrcholy nebo uzly. Každý uzel/vertex může být označen nebo neoznačen.
  • Hrany: Hrany jsou nakresleny nebo použity ke spojení dvou uzlů grafu. V orientovaném grafu lze uspořádat pár uzlů. Hrany mohou propojit libovolné dva uzly jakýmkoli možným způsobem. Neexistují žádná pravidla. Někdy jsou hrany známé také jako oblouky. Každá hrana může být označena/neoznačena.

Základní operace s grafy:

Níže jsou uvedeny základní operace na grafu:



  • Vložení uzlů/hran do grafu – Vložení uzlu do grafu.
  • Odstranění uzlů/hran v grafu – Odstraní uzel z grafu.
  • Vyhledávání v grafech – Hledání entity v grafu.
  • Traversal of Graphs – Procházení všech uzlů v grafu.

Aplikace grafu:

Níže jsou uvedeny reálné aplikace:

  • Grafové datové struktury lze použít k reprezentaci interakcí mezi hráči v týmu, jako jsou přihrávky, střely a útoky. Analýza těchto interakcí může poskytnout přehled o dynamice týmu a oblastech, které je třeba zlepšit.
  • Běžně se používá k reprezentaci sociálních sítí, jako jsou sítě přátel na sociálních médiích.
  • Grafy lze použít k znázornění topologie počítačových sítí, jako jsou spojení mezi směrovači a přepínači.
  • Grafy se používají k znázornění spojení mezi různými místy v dopravní síti, jako jsou silnice a letiště.
  • Grafy se používají v neuronových sítích, kde vrcholy představují neurony a hrany představují synapse mezi nimi. Neuronové sítě se používají k pochopení toho, jak funguje náš mozek a jak se mění spojení, když se učíme. Lidský mozek má asi 10^11 neuronů a téměř 10^15 synapsí.

Základy grafu:

BFS a DFS v grafu:

  • Šířka první průchod pro graf
  • Hloubka první průchod pro graf
  • Aplikace Depth First Search
  • Aplikace Breadth First Traversal
  • Iterativní hloubka první hledání
  • BFS pro Disconnected Graph
  • Transitivní uzavření grafu pomocí DFS
  • Rozdíl mezi BFS a DFS

Cykly v grafu:

  • Detekce cyklu v řízeném grafu
  • Detekce cyklu v neorientovaném grafu
  • Detekce cyklu v přímém grafu pomocí barev
  • Detekce negativního cyklu v grafu | (Bellman Ford)
  • Cykly délky n v neorientovaném a souvislém grafu
  • Detekce negativního cyklu pomocí Floyd Warshall
  • Klonujte řízený acyklický graf
  • Sjednocení podle pořadí a komprese cesty v algoritmu Union-Find
  • Nejkratší cesta v grafu:
    • Dijkstrův algoritmus nejkratší cesty
    • Bellman-Fordův algoritmus
    • Algoritmus Floyda Warshalla
    • Johnsonův algoritmus pro nejkratší cesty všech párů
    • Nejkratší cesta v řízeném acyklickém grafu
    • Algoritmus Dial
    • Vícestupňový graf (nejkratší cesta)
    • Nejkratší cesta v neváženém grafu
    • Karpův algoritmus minimálního středního (nebo průměrného) váhového cyklu
    • 0-1 BFS (nejkratší cesta v grafu binárních vah)
    • Najděte minimální cyklus hmotnosti v neorientovaném grafu

    Minimální kostra:

    • Prim's Minimum Spanning Tree (MST)
    • Kruskalův minimální algoritmus Spanning Tree
    • Rozdíl mezi Primovým a Kruskalovým algoritmem pro MST
    • Aplikace problému minimální kostry
    • Minimální náklady na připojení všech měst
    • Celkový počet Spanning Trees v grafu
    • Minimální produktová kostra
    • Obrácený algoritmus odstranění pro minimální kostru
    • Borůvkův algoritmus pro Minimum Spanning Tree

    Topologické řazení:

    • Topologické třídění
    • Všechny topologické druhy řízeného acyklického grafu
    • Kahnův algoritmus pro topologické třídění
    • Maximum hran, které lze přidat do DAG, takže zůstane DAG
    • Nejdelší cesta v řízeném acyklickém grafu
    • Topological Druh grafu využívající čas odchodu vrcholu

    Konektivita v grafu:

    • Artikulační body (nebo řezané vrcholy) v grafu
    • Biconnected Components
    • Mosty v grafu
    • Eulerovská cesta a okruh
    • Fleuryho algoritmus pro tisk Eulerovské cesty nebo okruhu
    • Silně propojené komponenty
    • Počítejte všechny možné cesty od zdroje k cíli s přesně k hranami
    • Eulerův obvod v orientovaném grafu
    • Délka nejkratšího řetězce k dosažení cílového slova
    • Zjistěte, zda lze pole řetězců zřetězit do kruhu
    • Tarjanův algoritmus k nalezení silně propojených komponent
    • Cesty pro cestování každým uzlem pomocí každé hrany (Sedm mostů Königsberg)
    • Dynamická konektivita | Sada 1 (přírůstkové)

    Maximální průtok v grafu:

    • Úvod do problému maximálního průtoku
    • Ford-Fulkersonův algoritmus pro problém maximálního průtoku
    • Najděte maximální počet hran disjunktních cest mezi dvěma vrcholy
    • Najděte minimální s-t řez v průtokové síti
    • Maximální bipartitní párování
    • Problém s přiřazením kanálu
    • Úvod do Push Relabel Algorithm
    • Kargerův algoritmus – sada 1 – Úvod a implementace
    • Dinicův algoritmus pro maximální průtok

    Někteří musí dělat problémy s grafem:

    • Najděte délku největší oblasti v Boolean Matrix
    • Spočítejte počet stromů v lese
    • Problém Petersonova grafu
    • Klonujte neorientovaný graf
    • Barvení grafů (úvod a aplikace)
    • Implementace problému cestovního obchodníka (TSP).
    • Problém krytu Vertex | Sada 1 (úvod a přibližný algoritmus)
    • Problém K Center | Sada 1 (Greedy přibližný algoritmus)
    • Erdos Renyl Model (pro generování náhodných grafů)
    • Čínský pošťák nebo inspekce trasy | Sada 1 (úvod)
    • Hierholzerův algoritmus pro orientovaný graf
    • Zkontrolujte, zda je daný graf bipartitní nebo ne
    • Problém hada a žebříku
    • Boggle (Najděte všechna možná slova na desce znaků)
    • Hopcroft Karpův algoritmus pro maximální párování-úvod
    • Minimální doba pro hnilobu všech pomerančů
    • Sestrojte graf z daných stupňů všech vrcholů
    • Určete, zda v orientovaném grafu existuje univerzální jímka
    • Počet propadových uzlů v grafu
    • Problém dvou klik (Zkontrolujte, zda lze graf rozdělit na dvě kliky)

    Některé kvízy:

    • Kvízy na Graph Traversal
    • Kvízy na nejkratší cestě grafu
    • Kvízy o grafu minimální kostry
    • Kvízy o grafech

    Rychlé odkazy :

    • 10 nejčastějších otázek k rozhovoru o hloubkovém prvním vyhledávání (DFS)
    • Některé zajímavé otázky o nejkratší cestě
    • Videa v grafech

    Doporučeno:

    • Naučte se datovou strukturu a algoritmy | Výukový program DSA