logo

TechCodeview

Struktura podatkov grafa in algoritmi

Struktura podatkov grafa je zbirka vozlišča povezan z robovi . Uporablja se za predstavitev odnosov med različnimi entitetami. Grafni algoritmi so metode, ki se uporabljajo za manipulacijo in analizo grafov, reševanje različnih problemov, kot so iskanje najkrajše poti oz zaznavanje ciklov.

java lambda



Kazalo

Komponente grafa:

  • Oglišča: Točke so temeljne enote grafa. Včasih so oglišča znana tudi kot oglišča ali vozlišča. Vsako vozlišče/vozlišče je lahko označeno ali neoznačeno.
  • Robovi: Robovi so narisani ali uporabljeni za povezavo dveh vozlišč grafa. Lahko je urejen par vozlišč v usmerjenem grafu. Robovi lahko povežejo katerikoli dve vozlišči na kateri koli možen način. Pravil ni. Včasih so robovi znani tudi kot loki. Vsak rob je lahko označen/neoznačen.

Osnovne operacije na grafih:

Spodaj so osnovne operacije na grafu:



  • Vstavljanje vozlišč/robov v graf – vstavite vozlišče v graf.
  • Brisanje vozlišč/robov v grafu – izbrišite vozlišče iz grafa.
  • Iskanje po grafih – poiščite entiteto v grafu.
  • Prehod grafov – Prehod vseh vozlišč v grafu.

Aplikacije grafa:

Sledijo aplikacije iz resničnega življenja:

  • Podatkovne strukture grafov je mogoče uporabiti za predstavitev interakcij med igralci v ekipi, kot so podaje, streli in preboji. Analiza teh interakcij lahko zagotovi vpogled v dinamiko ekipe in področja za izboljšave.
  • Običajno se uporablja za predstavljanje družbenih omrežij, kot so omrežja prijateljev na družbenih medijih.
  • Grafe je mogoče uporabiti za predstavitev topologije računalniških omrežij, kot so povezave med usmerjevalniki in stikali.
  • Grafi se uporabljajo za predstavitev povezav med različnimi kraji v prometnem omrežju, kot so ceste in letališča.
  • Grafi se uporabljajo v nevronskih mrežah, kjer oglišča predstavljajo nevrone, robovi pa sinapse med njimi. Nevronske mreže se uporabljajo za razumevanje delovanja naših možganov in kako se povezave spreminjajo, ko se učimo. Človeški možgani imajo približno 10^11 nevronov in skoraj 10^15 sinaps.

Osnove grafa:

BFS in DFS v grafu:

  • Prvi prehod v širino za graf
  • Prvo prečkanje globine za graf
  • Uporaba globinskega iskanja
  • Aplikacije prehoda prve širine
  • Iterativno iskanje po globini
  • BFS za nepovezani graf
  • Tranzitivno zaprtje grafa z uporabo DFS
  • Razlika med BFS in DFS

Cikli v grafu:

  • Zaznavanje cikla v usmerjenem grafu
  • Zaznaj cikel v neusmerjenem grafu
  • Zaznaj cikel v neposrednem grafu z uporabo barv
  • Zaznaj negativen cikel v grafu | (Bellman Ford)
  • Cikli dolžine n v neusmerjenem in povezanem grafu
  • Odkrivanje negativnega cikla s pomočjo Floyda Warshall
  • Klonirajte usmerjeni aciklični graf
  • Združitev po rangu in stiskanje poti v algoritmu iskanja unije
  • Najkrajša pot v grafu:
    • Dijkstrajev algoritem najkrajše poti
    • Bellman-Fordov algoritem
    • Floyd Warshallov algoritem
    • Johnsonov algoritem za najkrajše poti vseh parov
    • Najkrajša pot v usmerjenem acikličnem grafu
    • Dialov algoritem
    • Večstopenjski graf (najkrajša pot)
    • Najkrajša pot v neobteženem grafu
    • Karpov algoritem cikla minimalne srednje (ali povprečne) teže
    • 0-1 BFS (najkrajša pot v binarnem grafu teže)
    • Poiščite cikel najmanjše teže v neusmerjenem grafu

    Najmanjše vpeto drevo:

    • Primovo minimalno vpeto drevo (MST)
    • Kruskalov algoritem minimalnega vpetega drevesa
    • Razlika med Primovim in Kruskalovim algoritmom za MST
    • Uporaba problema minimalnega vpetega drevesa
    • Minimalni stroški za povezavo vseh mest
    • Skupno število vpetih dreves v grafu
    • Minimalno vpeto drevo izdelka
    • Algoritem za obratno brisanje za minimalno vpeto drevo
    • Boruvkov algoritem za minimalno vpeto drevo

    Topološko razvrščanje:

    • Topološko razvrščanje
    • Vse topološke vrste usmerjenega acikličnega grafa
    • Kahnov algoritem za topološko razvrščanje
    • Največje število robov, ki jih je mogoče dodati v DAG, tako da ostane DAG
    • Najdaljša pot v usmerjenem acikličnem grafu
    • Topološka vrsta grafa z uporabo časa odhoda vozlišča

    Povezljivost v Graphu:

    • Artikulacijske točke (ali rezana oglišča) v grafu
    • Bipovezane komponente
    • Mostovi v grafu
    • Eulerjeva pot in krog
    • Fleuryjev algoritem za tiskanje Eulerjeve poti ali vezja
    • Močno povezane komponente
    • Preštej vse možne hoje od vira do cilja s točno k robovi
    • Eulerjevo vezje v usmerjenem grafu
    • Dolžina najkrajše verige za doseganje ciljne besede
    • Ugotovite, ali je niz nizov mogoče verižiti v krog
    • Tarjanov algoritem za iskanje močno povezanih komponent
    • Poti za potovanje po vsakem vozlišču z uporabo vsakega roba (Sedem mostov Königsberga)
    • Dinamična povezljivost | Niz 1 (inkrementalno)

    Največji pretok v grafu:

    • Uvod v problem največjega pretoka
    • Ford-Fulkersonov algoritem za problem največjega pretoka
    • Poiščite največje število robno ločenih poti med dvema vozliščema
    • Poiščite najmanjši s-t rez v pretočni mreži
    • Največje dvodelno ujemanje
    • Težava z dodelitvijo kanala
    • Uvod v algoritem Push Relabel
    • Kargerjev algoritem - sklop 1 - Uvod in izvedba
    • Dinicov algoritem za največji pretok

    Nekateri morajo narediti težave na grafu:

    • Poiščite dolžino največjega območja v logični matriki
    • Preštejte število dreves v gozdu
    • Problem Petersonovega grafa
    • Klonirajte neusmerjeni graf
    • Barvanje grafov (uvod in aplikacije)
    • Izvedba problema trgovskega potnika (TSP).
    • Težava s pokrovom Vertex | 1. sklop (uvod in približni algoritem)
    • Težava s centri K | 1. niz (pohlepni približni algoritem)
    • Model Erdos Renyl (za generiranje naključnih grafov)
    • Kitajski poštar ali pregled poti | Komplet 1 (uvod)
    • Hierholzerjev algoritem za usmerjeni graf
    • Preverite, ali je dani graf dvodelni ali ne
    • Problem s kačo in lestvijo
    • Boggle (Poišči vse možne besede na tabli znakov)
    • Hopcroft Karpov algoritem za maksimalno ujemanje-Uvod
    • Minimalni čas za gnitje vseh pomaranč
    • Zgradite graf iz danih stopinj vseh oglišč
    • Ugotovite, ali v usmerjenem grafu obstaja univerzalni ponor
    • Število ponornih vozlišč v grafu
    • Problem dveh klik (preverite, ali je mogoče graf razdeliti na dva klika)

    Nekaj ​​kvizov:

    • Kvizi o Graph Traversal
    • Kvizi o grafu Najkrajša pot
    • Kvizi o Graph Minimum Spanning Tree
    • Kvizi o grafih

    Hitre povezave :

    • 10 najpogostejših vprašanj na intervjuju o globinskem iskanju (DFS)
    • Nekaj ​​zanimivih vprašanj o najkrajši poti
    • Videoposnetki o grafih

    Priporočeno:

    • Naučite se podatkovne strukture in algoritmov | Vadnica DSA