Štruktúra údajov grafu je zbierka uzly pripojený pomocou hrany . Používa sa na znázornenie vzťahov medzi rôznymi entitami. Grafové algoritmy sú metódy používané na manipuláciu a analýzu grafov, riešenie rôznych problémov ako napr nájsť najkratšiu cestu alebo detekčné cykly.

bash polia

Obsah

• Komponenty grafu
• Základné operácie s grafmi
• Aplikácie grafu
• Základy grafu
• BFS a DFS v grafe
• Cykly v grafe
• Najkratšia cesta v grafe
• Minimálny kostra
• Topologické triedenie
• Konektivita v grafe
• Maximálny prietok v grafe
• Niektorí musia robiť problémy s grafom
• Niektoré kvízy

Komponenty grafu:

• Vrcholy: Vrcholy sú základnými jednotkami grafu. Niekedy sú vrcholy známe aj ako vrcholy alebo uzly. Každý uzol/vertex môže byť označený alebo neoznačený.
• Hrany: Hrany sú nakreslené alebo použité na spojenie dvoch uzlov grafu. Môže byť usporiadaný pár uzlov v orientovanom grafe. Hrany môžu akýmkoľvek možným spôsobom spájať akékoľvek dva uzly. Neexistujú žiadne pravidlá. Niekedy sú hrany známe aj ako oblúky. Každá hrana môže byť označená/neoznačená.

Základné operácie s grafmi:

Nižšie sú uvedené základné operácie na grafe:

• Vloženie uzlov/hran do grafu – Vloženie uzla do grafu.
• Vymazanie uzlov/hran v grafe – Vymaže uzol z grafu.
• Vyhľadávanie v grafoch – Vyhľadajte entitu v grafe.
• Traversal of Graphs – Prechádzanie všetkých uzlov v grafe.

Aplikácie grafu:

Nasledujú aplikácie v reálnom živote:

• Štruktúry grafových údajov možno použiť na znázornenie interakcií medzi hráčmi v tíme, ako sú prihrávky, strely a zákroky. Analýza týchto interakcií môže poskytnúť prehľad o dynamike tímu a oblastiach na zlepšenie.
• Bežne sa používa na označenie sociálnych sietí, ako sú siete priateľov na sociálnych médiách.
• Grafy možno použiť na znázornenie topológie počítačových sietí, ako sú napríklad spojenia medzi smerovačmi a prepínačmi.
• Grafy sa používajú na znázornenie spojení medzi rôznymi miestami v dopravnej sieti, ako sú cesty a letiská.
• Grafy sa používajú v neurónových sieťach, kde vrcholy predstavujú neuróny a hrany predstavujú synapsie medzi nimi. Neurónové siete sa používajú na pochopenie toho, ako funguje náš mozog a ako sa menia spojenia, keď sa učíme. Ľudský mozog má asi 10^11 neurónov a takmer 10^15 synapsií.

Základy grafu:

• Úvod do grafov
• Graf a jeho znázornenie
• Typy grafov s príkladmi
• Základné vlastnosti grafu
• Aplikácie, výhody a nevýhody grafu
• Transponovať graf
• Rozdiel medzi grafom a stromom

BFS a DFS v grafe:

• Prvý prechod na šírku grafu
• Prvý prechod do hĺbky pre graf
• Aplikácie hĺbkového prvého vyhľadávania
• Aplikácie Breadth First Traversal
• Iteratívne hĺbkové prvé vyhľadávanie
• BFS pre Disconnected Graph
• Tranzitívne uzavretie grafu pomocou DFS
• Rozdiel medzi BFS a DFS

Cykly v grafe:

• Detekcia cyklu v riadenom grafe
• Detekcia cyklu v neorientovanom grafe
• Detekcia cyklu v priamom grafe pomocou farieb
• Zistiť negatívny cyklus v grafe | (Bellman Ford)
• Cykly dĺžky n v neusmernenom a súvislom grafe
• Detekcia negatívneho cyklu pomocou Floyd Warshall
• Klonujte riadený acyklický graf
• Zjednotenie podľa poradia a kompresie cesty v algoritme Union-Find
• Najkratšia cesta v grafe:
  • Dijkstrov algoritmus najkratšej cesty
  • Bellman-Fordov algoritmus
  • Algoritmus Floyda Warshalla
  • Johnsonov algoritmus pre najkratšie cesty všetkých párov
  • Najkratšia cesta v riadenom acyklickom grafe
  • Algoritmus číselníka
  • Viacstupňový graf (najkratšia cesta)
  • Najkratšia cesta v neváženom grafe
  • Karpov algoritmus cyklu minimálnej strednej (alebo priemernej) hmotnosti
  • 0-1 BFS (najkratšia cesta v grafe binárnych váh)
  • Nájdite minimálny cyklus hmotnosti v neorientovanom grafe

  Minimálny kostrový strom:

  • Primov minimálny spanningový strom (MST)
  • Kruskalov algoritmus minimálneho spanningového stromu
  • Rozdiel medzi Primovým a Kruskalovým algoritmom pre MST
  • Aplikácie problému minimálneho kostrového stromu
  • Minimálne náklady na pripojenie všetkých miest
  • Celkový počet kostrových stromov v grafe
  • Minimálny produktový strom
  • Obrátený algoritmus vymazania pre minimálny Spanning Tree
  • Borůvkov algoritmus pre minimálny kostrový strom

  Topologické triedenie:

  • Topologické triedenie
  • Všetky topologické druhy riadeného acyklického grafu
  • Kahnov algoritmus pre topologické triedenie
  • Maximálny počet hrán, ktoré je možné pridať do DAG, takže zostane DAG
  • Najdlhšia cesta v riadenom acyklickom grafe
  • Topologické Triedenie grafu pomocou času odchodu vrcholu

  Konektivita v grafe:

  • Artikulačné body (alebo rezané vrcholy) v grafe
  • Obojstranne prepojené komponenty
  • Mosty v grafe
  • Eulerovská cesta a okruh
  • Fleuryho algoritmus na tlač eulerovskej cesty alebo okruhu
  • Silne pripojené komponenty
  • Spočítajte všetky možné prechádzky od zdroja k cieľu s presne k hranami
  • Eulerov obvod v riadenom grafe
  • Dĺžka najkratšej reťaze na dosiahnutie cieľového slova
  • Zistite, či je možné reťazec reťazcov vytvoriť do kruhu
  • Tarjanov algoritmus na nájdenie silne prepojených komponentov
  • Cesty na cestovanie jednotlivými uzlami pomocou každej hrany (Sedem mostov Königsbergu)
  • Dynamická konektivita | Sada 1 (prírastkové)

  Maximálny prietok v grafe:

  • Úvod do problému maximálneho prietoku
  • Ford-Fulkersonov algoritmus pre problém maximálneho prietoku
  • Nájdite maximálny počet okrajových disjunktných ciest medzi dvoma vrcholmi
  • Nájdite minimálny s-t rez v prietokovej sieti
  • Maximálna bipartitná zhoda
  • Problém s priradením kanálov
  • Úvod do algoritmu Push Relabel Algorithm
  • Kargerov súbor algoritmov 1 - Úvod a implementácia
  • Dinicov algoritmus pre maximálny prietok

  Niektorí musia robiť problémy s grafom:

  • Nájdite dĺžku najväčšieho regiónu v Boolean Matrix
  • Spočítajte počet stromov v lese
  • Problém Petersonovho grafu
  • Klonujte neorientovaný graf
  • Farbenie grafu (Úvod a aplikácie)
  • Implementácia problému cestujúceho obchodníka (TSP).
  • Problém krytu vertexu | Sada 1 (úvod a približný algoritmus)
  • Problém K Center | Sada 1 (Greedy približný algoritmus)
  • Model Erdos Renyl (na generovanie náhodných grafov)
  • Čínsky poštár alebo kontrola trasy | Sada 1 (úvod)
  • Hierholzerov algoritmus pre orientovaný graf
  • Skontrolujte, či je daný graf bipartitný alebo nie
  • Problém hada a rebríka
  • Boggle (nájdite všetky možné slová na tabuli so znakmi)
  • Hopcroft Karpov algoritmus pre maximálnu zhodu-Úvod
  • Minimálny čas na hnilobu všetkých pomarančov
  • Zostrojte graf z daných stupňov všetkých vrcholov
  • Zistite, či v orientovanom grafe existuje univerzálny drez
  • Počet klesajúcich uzlov v grafe
  • Problém dvoch klikov (skontrolujte, či je možné graf rozdeliť na dve kliky)

  Niektoré kvízy:

  • Kvízy o prechádzaní grafom
  • Kvízy na najkratšej ceste grafu
  • Kvízy o minimálnom kostre grafu
  • Kvízy o grafoch

  Rýchle odkazy:

  • 10 najčastejších otázok v rozhovore o hĺbkovom prvom vyhľadávaní (DFS)
  • Niekoľko zaujímavých otázok o najkratšej ceste
  • Videá v grafoch

  Odporúčané:

  • Naučte sa dátovú štruktúru a algoritmy | Príručka DSA