Grafisk datastruktur er en samling av noder forbundet med kanter . Det brukes til å representere forhold mellom ulike enheter. Grafiske algoritmer er metoder som brukes til å manipulere og analysere grafer, løse ulike problemer som finne den korteste veien eller oppdage sykluser.
aryan khan
Innholdsfortegnelse
- Komponenter i en graf
- Grunnleggende operasjoner på grafer
- Anvendelser av Graph
- Grunnleggende om Graph
- BFS og DFS i Graph
- Sykluser i graf
- Korteste vei i grafen
- Minimum Spanning Tree
- Topologisk sortering
- Tilkobling i Graph
- Maksimal flyt i graf
- Noen må gjøre Problemer på graf
- Noen quiz
Komponenter i en graf:
- Topppunkter: Toppunktene er de grunnleggende enhetene i grafen. Noen ganger er toppunkter også kjent som toppunkt eller noder. Hver node/vertex kan være merket eller umerket.
- Kanter: Kanter tegnes eller brukes til å koble sammen to noder i grafen. Det kan bestilles par med noder i en rettet graf. Edges kan koble sammen hvilke som helst to noder på alle mulige måter. Det er ingen regler. Noen ganger er kanter også kjent som buer. Hver kant kan merkes/ikke merkes.
Grunnleggende operasjoner på grafer:
Nedenfor er de grunnleggende operasjonene på grafen:
- Innsetting av noder/kanter i grafen – Sett inn en node i grafen.
- Sletting av noder/kanter i grafen – Slett en node fra grafen.
- Søke på grafer – Søk etter en enhet i grafen.
- Traversering av grafer – Gjennomgå alle nodene i grafen.
Anvendelser av graf:
Følgende er de virkelige applikasjonene:
- Grafdatastrukturer kan brukes til å representere interaksjonene mellom spillere på et lag, for eksempel pasninger, skudd og taklinger. Å analysere disse interaksjonene kan gi innsikt i teamdynamikk og områder for forbedring.
- Vanligvis brukt til å representere sosiale nettverk, for eksempel nettverk av venner på sosiale medier.
- Grafer kan brukes til å representere topologien til datanettverk, for eksempel forbindelsene mellom rutere og svitsjer.
- Grafer brukes til å representere sammenhengene mellom ulike steder i et transportnettverk, for eksempel veier og flyplasser.
- Grafer brukes i nevrale nettverk der hjørner representerer nevroner og kanter representerer synapsene mellom dem. Nevrale nettverk brukes til å forstå hvordan hjernen vår fungerer og hvordan forbindelser endres når vi lærer. Den menneskelige hjernen har omtrent 10^11 nevroner og nær 10^15 synapser.
Grunnleggende om graf:
- Introduksjon til grafer
- Grafen og dens representasjoner
- Typer grafer med eksempler
- Grunnleggende egenskaper for en graf
- Bruksområder, fordeler og ulemper med Graph
- Transponer graf
- Forskjellen mellom graf og tre
BFS og DFS i graf:
- Breadth First Traversal for en graf
- Depth First Traversal for en graf
- Anvendelser av Depth First Search
- Anvendelser av Breadth First Traversal
- Iterativ dybde først søk
- BFS for Disconnected Graph
- Transitiv lukking av en graf ved bruk av DFS
- Forskjellen mellom BFS og DFS
Sykluser i graf:
- Oppdag syklus i en rettet graf
- Registrer syklus i en urettet graf
- Oppdag syklus i en direkte graf ved hjelp av farger
- Oppdag en negativ syklus i en graf | (Bellman Ford)
- Sykluser med lengde n i en urettet og koblet graf
- Oppdager negativ syklus ved hjelp av Floyd Warshall
- Klone en rettet asyklisk graf
- Union etter rangering og banekomprimering i Union-Find Algorithm
- Korteste vei i grafen:
- Dijkstras korteste vei-algoritme
- Bellman–Ford-algoritme
- Floyd Warshall-algoritme
- Johnsons algoritme for alle-par korteste veier
- Korteste vei i rettet asyklisk graf
- Dial sin algoritme
- Flertrinns graf (korteste bane)
- Korteste vei i en uvektet graf
- Karps minste gjennomsnittlige (eller gjennomsnittlige) vektsyklusalgoritme
- 0-1 BFS (korteste vei i en binær vektgraf)
- Finn minimum vektsyklus i en urettet graf
Minimum spannende tre:
- Prims minimum spanning-tre (MST)
- Kruskals Minimum Spanning Tree Algorithm
- Forskjellen mellom Prims og Kruskals algoritme for MST
- Anvendelser av Minimum Spanning Tree Problem
- Minimumskostnad for å koble sammen alle byer
- Totalt antall spannende trær i en graf
- Minimum produktspenningstre
- Omvendt slettealgoritme for minimumsspenningstre
- Boruvkas algoritme for Minimum Spanning Tree
Topologisk sortering:
- Topologisk sortering
- Alle topologiske typer en rettet asyklisk graf
- Kahns algoritme for topologisk sortering
- Maksimal kanter som kan legges til DAG slik at det forblir DAG
- Lengste vei i en rettet asyklisk graf
- Topologisk type graf som bruker avgangstiden for toppunktet
Tilkobling i graf:
- Artikulasjonspunkter (eller kuttede hjørner) i en graf
- Bikoblede komponenter
- Broer i en graf
- Eulerian sti og krets
- Fleurys algoritme for utskrift av Eulerian Path eller Circuit
- Sterkt tilkoblede komponenter
- Tell alle mulige turer fra en kilde til en destinasjon med nøyaktig k kanter
- Euler-krets i en rettet graf
- Lengde på korteste kjede for å nå målordet
- Finn om en rekke strenger kan lenkes for å danne en sirkel
- Tarjans algoritme for å finne sterkt tilkoblede komponenter
- Veier for å reise hver node ved å bruke hver kant (Seven Bridges of Königsberg)
- Dynamisk tilkobling | Sett 1 (inkrementelt)
Maksimal flyt i graf:
- Max Flow Problem Introduksjon
- Ford-Fulkerson-algoritme for maksimal strømningsproblem
- Finn maksimalt antall kantadskillende baner mellom to toppunkter
- Finn minimum s-t kutt i et strømningsnettverk
- Maksimal todelt matching
- Problem med kanaltilordning
- Introduksjon til Push Relabel Algorithm
- Kargers algoritme - sett 1 - introduksjon og implementering
- Dinics algoritme for maksimal flyt
Noen må gjøre problemer på grafen:
- Finn lengden på den største regionen i boolsk matrise
- Tell antall trær i en skog
- Et Peterson-grafproblem
- Klone en udirigert graf
- Graffarging (introduksjon og applikasjoner)
- Implementering av Traveling Salesman Problem (TSP).
- Vertex Cover Problem | Sett 1 (introduksjon og omtrentlig algoritme)
- K Centers Problem | Sett 1 (Grådig omtrentlig algoritme)
- Erdos Renyl-modell (for generering av tilfeldige grafer)
- Kinesisk postmann eller ruteinspeksjon | Sett 1 (introduksjon)
- Hierholzers algoritme for rettet graf
- Sjekk om en gitt graf er todelt eller ikke
- Problem med slange og stige
- Boggle (Finn alle mulige ord i en tavle med tegn)
- Hopcroft Karp Algorithm for Maximum Matching-Introduksjon
- Minimum tid for å råtne alle appelsiner
- Konstruer en graf fra gitte grader av alle toppunkter
- Finn ut om det finnes en universell vask i en rettet graf
- Antall synknoder i en graf
- To klikk-problem (sjekk om grafen kan deles i to klikker)
Noen quiz:
- Quiz om Graph Traversal
- Spørrekonkurranser om Graph Shortest Path
- Spørrekonkurranser om Graph Minimum Spanning Tree
- Quiz om grafer
Hurtigkoblinger :
- Topp 10 intervjuspørsmål om Depth First Search (DFS)
- Noen interessante korteste vei-spørsmål
- Videoer på Graphs
Anbefalt:
- Lær datastruktur og algoritmer | DSA veiledning