Graf datastruktur er en samling af noder forbundet med kanter . Det bruges til at repræsentere relationer mellem forskellige enheder. Grafiske algoritmer er metoder, der bruges til at manipulere og analysere grafer, løse forskellige problemer som f.eks at finde den korteste vej eller detektering af cyklusser.
cout
Indholdsfortegnelse
- Komponenter i en graf
- Grundlæggende handlinger på grafer
- Anvendelser af Graph
- Grundlæggende om graf
- BFS og DFS i Graph
- Cykler i graf
- Korteste vej i graf
- Minimumsspændende træ
- Topologisk sortering
- Forbindelse i Graph
- Maksimalt flow i graf
- Nogle skal lave Problemer på Graph
- Nogle quizzer
Komponenter i en graf:
- Hjørner: Toppunkter er grafens grundlæggende enheder. Nogle gange er toppunkter også kendt som vertex eller noder. Hver node/vertex kan være mærket eller umærket.
- Kanter: Kanter tegnes eller bruges til at forbinde to knudepunkter på grafen. Det kan bestilles par noder i en rettet graf. Edges kan forbinde alle to noder på enhver mulig måde. Der er ingen regler. Nogle gange er kanter også kendt som buer. Hver kant kan mærkes/ikke mærkes.
Grundlæggende handlinger på grafer:
Nedenfor er de grundlæggende handlinger på grafen:
- Indsættelse af noder/kanter i grafen – Indsæt en node i grafen.
- Sletning af noder/kanter i grafen – Slet en node fra grafen.
- Søgning på grafer – Søg efter en enhed i grafen.
- Gennemgang af grafer – Gennemgang af alle knudepunkter i grafen.
Anvendelser af graf:
Følgende er de virkelige applikationer:
- Grafdatastrukturer kan bruges til at repræsentere interaktionerne mellem spillere på et hold, såsom afleveringer, skud og tacklinger. Analyse af disse interaktioner kan give indsigt i teamdynamik og områder til forbedring.
- Almindeligvis brugt til at repræsentere sociale netværk, såsom netværk af venner på sociale medier.
- Grafer kan bruges til at repræsentere topologien af computernetværk, såsom forbindelserne mellem routere og switches.
- Grafer bruges til at repræsentere forbindelserne mellem forskellige steder i et transportnetværk, såsom veje og lufthavne.
- Grafer bruges i neurale netværk, hvor hjørner repræsenterer neuroner og kanter repræsenterer synapserne mellem dem. Neurale netværk bruges til at forstå, hvordan vores hjerne fungerer, og hvordan forbindelser ændrer sig, når vi lærer. Den menneskelige hjerne har omkring 10^11 neuroner og tæt på 10^15 synapser.
Grundlæggende om graf:
- Introduktion til grafer
- Graf og dens repræsentationer
- Typer af grafer med eksempler
- Grundlæggende egenskaber for en graf
- Anvendelser, fordele og ulemper ved Graph
- Transponer graf
- Forskellen mellem graf og træ
BFS og DFS i graf:
- Breadth First Traversal for en graf
- Dybde første gennemløb for en graf
- Anvendelser af Depth First Search
- Anvendelser af Breadth First Traversal
- Iterativ dybde først søgning
- BFS for Disconnected Graph
- Transitiv lukning af en graf ved hjælp af DFS
- Forskellen mellem BFS og DFS
Cykler i graf:
- Registrer cyklus i en rettet graf
- Detekter cyklus i en urettet graf
- Registrer cyklus i en direkte graf ved hjælp af farver
- Registrer en negativ cyklus i en graf | (Bellman Ford)
- Cykler af længden n i en urettet og forbundet graf
- Registrerer negativ cyklus ved hjælp af Floyd Warshall
- Klon en rettet acyklisk graf
- Union efter rang og sti-komprimering i Union-Find-algoritme
- Korteste vej i grafen:
- Dijkstras korteste vejs algoritme
- Bellman-Ford algoritme
- Floyd Warshall algoritme
- Johnsons algoritme for alle-par korteste veje
- Korteste vej i rettet acyklisk graf
- Urskivens algoritme
- Flertrinsgraf (korteste sti)
- Korteste vej i en uvægtet graf
- Karps minimumsmiddel (eller gennemsnitlige) vægtcyklusalgoritme
- 0-1 BFS (korteste vej i en binær vægtgraf)
- Find minimumsvægtcyklus i en urettet graf
Minimumsspændende træ:
- Prim's Minimum Spanning Tree (MST)
- Kruskals Minimum Spanning Tree Algorithm
- Forskel mellem Prims og Kruskals algoritme for MST
- Anvendelser af Minimum Spanning Tree Problem
- Minimumsomkostninger for at forbinde alle byer
- Samlet antal spændende træer i en graf
- Minimumsprodukt spænder træ
- Omvendt sletningsalgoritme for minimumsspændingstræ
- Boruvkas algoritme for Minimum Spanning Tree
Topologisk sortering:
- Topologisk sortering
- Alle topologiske former for en rettet acyklisk graf
- Kahns algoritme for topologisk sortering
- Maksimale kanter, der kan tilføjes til DAG, så det forbliver DAG
- Længste vej i en rettet acyklisk graf
- Topologisk sortering af en graf, der bruger toppunktets afgangstid
Forbindelse i graf:
- Artikulationspunkter (eller afskårne hjørner) i en graf
- Biforbundne komponenter
- Broer i en graf
- Eulerian sti og kredsløb
- Fleurys algoritme til udskrivning af Eulerian Path eller Circuit
- Stærkt forbundne komponenter
- Tæl alle mulige ture fra en kilde til en destination med præcis k kanter
- Euler-kredsløb i en rettet graf
- Længde på korteste kæde for at nå målordet
- Find ud af, om en række strenge kan kædes sammen for at danne en cirkel
- Tarjans algoritme til at finde stærkt forbundne komponenter
- Stier til at rejse hver noder ved hjælp af hver kant (Seven Bridges of Königsberg)
- Dynamisk forbindelse | Sæt 1 (inkremental)
Maksimalt flow i graf:
- Max Flow Problem Introduktion
- Ford-Fulkerson-algoritme for maksimalt flowproblem
- Find det maksimale antal kantadskillende baner mellem to spidser
- Find minimum s-t cut i et flownetværk
- Maksimal Bipartite Matching
- Problem med kanaltildeling
- Introduktion til Push Relabel Algorithm
- Kargers algoritme - Sæt 1 - Introduktion og implementering
- Dinics algoritme for maksimalt flow
Nogle skal lave problemer på graf:
- Find længden af den største region i Boolean Matrix
- Tæl antallet af træer i en skov
- Et Peterson-grafproblem
- Klon en udirigeret graf
- Graffarvning (introduktion og applikationer)
- Implementering af Traveling Salesman Problem (TSP).
- Vertex Cover Problem | Sæt 1 (Introduktion og omtrentlig algoritme)
- K Centers Problem | Sæt 1 (Grådig omtrentlig algoritme)
- Erdos Renyl Model (til generering af tilfældige grafer)
- Kinesisk postbud eller ruteinspektion | Sæt 1 (introduktion)
- Hierholzers algoritme for rettet graf
- Tjek om en given graf er todelt eller ej
- Problem med slange og stige
- Boggle (Find alle mulige ord i en tavle af tegn)
- Hopcroft Karp Algorithm for Maximum Matching-Introduktion
- Minimum tid til at rådne alle appelsiner
- Konstruer en graf ud fra givne grader af alle hjørner
- Bestem, om der findes en universel vask i en rettet graf
- Antal synknoder i en graf
- To klik-problem (tjek om grafen kan opdeles i to kliker)
Nogle quizzer:
- Quizzer om Graph Traversal
- Quizzer om Graph Shortest Path
- Quizzer om Graph Minimum Spanning Tree
- Quizzer om grafer
Hurtige links :
- Top 10 interviewspørgsmål om Depth First Search (DFS)
- Nogle interessante korteste vej spørgsmål
- Videoer på grafer
Anbefalede:
- Lær datastruktur og algoritmer | DSA Tutorial