logo

TechCodeview

Grafiekgegevensstructuur en algoritmen

Grafiekgegevensstructuur is een verzameling van knooppunten verbonden door randen . Het wordt gebruikt om relaties tussen verschillende entiteiten weer te geven. Grafiekalgoritmen zijn methoden die worden gebruikt om grafieken te manipuleren en analyseren, en verschillende problemen op te lossen, zoals het vinden van de kortste weg of cycli detecteren.

cm naar voet en inch



Inhoudsopgave

Componenten van een grafiek:

  • Hoekpunten: Hoekpunten zijn de fundamentele eenheden van de grafiek. Soms worden hoekpunten ook wel hoekpunten of knooppunten genoemd. Elk knooppunt/hoekpunt kan gelabeld of ongelabeld zijn.
  • Randen: Randen worden getekend of gebruikt om twee knooppunten van de grafiek met elkaar te verbinden. Er kan een paar knooppunten in een gerichte grafiek worden besteld. Randen kunnen twee willekeurige knooppunten op elke mogelijke manier met elkaar verbinden. Er zijn geen regels. Soms worden randen ook wel bogen genoemd. Elke rand kan worden gelabeld/ongelabeld.

Basisbewerkingen op grafieken:

Hieronder staan ​​de basisbewerkingen in de grafiek:



  • Invoegen van knooppunten/randen in de grafiek – Voeg een knooppunt in de grafiek in.
  • Verwijdering van knooppunten/randen in de grafiek – Verwijder een knooppunt uit de grafiek.
  • Zoeken in grafieken – Zoek een entiteit in de grafiek.
  • Doorkruisen van grafieken – Doorkruisen van alle knooppunten in de grafiek.

Toepassingen van grafiek:

Hieronder volgen de real-life toepassingen:

  • Grafiekgegevensstructuren kunnen worden gebruikt om de interacties tussen spelers in een team weer te geven, zoals passes, schoten en tackles. Het analyseren van deze interacties kan inzicht verschaffen in de teamdynamiek en verbeterpunten.
  • Wordt vaak gebruikt om sociale netwerken weer te geven, zoals netwerken van vrienden op sociale media.
  • Grafieken kunnen worden gebruikt om de topologie van computernetwerken weer te geven, zoals de verbindingen tussen routers en switches.
  • Grafieken worden gebruikt om de verbindingen tussen verschillende plaatsen in een transportnetwerk weer te geven, zoals wegen en luchthavens.
  • Grafieken worden gebruikt in neurale netwerken waarbij hoekpunten neuronen vertegenwoordigen en randen de synapsen ertussen. Neurale netwerken worden gebruikt om te begrijpen hoe onze hersenen werken en hoe verbindingen veranderen als we leren. Het menselijk brein heeft ongeveer 10^11 neuronen en bijna 10^15 synapsen.

Basisprincipes van grafiek:

BFS en DFS in grafiek:

  • Breedte Eerste verplaatsing voor een grafiek
  • Diepte Eerste Traversal voor een grafiek
  • Toepassingen van Depth First Search
  • Toepassingen van breedte-eerste traversal
  • Iteratieve diepte eerste zoekopdracht
  • BFS voor verbroken grafiek
  • Transitieve afsluiting van een grafiek met DFS
  • Verschil tussen BFS en DFS

Cycli in grafiek:

  • Cyclus detecteren in een gerichte grafiek
  • Detecteer cyclus in een ongerichte grafiek
  • Detecteer cyclus in een directe grafiek met behulp van kleuren
  • Detecteer een negatieve cyclus in een grafiek | (Bellman Ford)
  • Cycli met lengte n in een ongerichte en verbonden graaf
  • Detecteren van een negatieve cyclus met behulp van Floyd Warshall
  • Kloon een gerichte acyclische grafiek
  • Union By Rank en Path-compressie in Union-Find-algoritme
  • Kortste pad in grafiek:
    • Het kortste pad-algoritme van Dijkstra
    • Bellman-Ford-algoritme
    • Floyd Warshall-algoritme
    • Johnson's algoritme voor de kortste paden van alle paren
    • Kortste pad in gerichte acyclische grafiek
    • Het algoritme van Dial
    • Meertrapsgrafiek (kortste pad)
    • Kortste pad in een ongewogen grafiek
    • Karp's minimale gemiddelde (of gemiddelde) gewichtscyclusalgoritme
    • 0-1 BFS (kortste pad in een binaire gewichtsgrafiek)
    • Zoek de minimale gewichtscyclus in een ongerichte grafiek

    Minimale spanningsboom:

    • Prim's Minimum Spanning Tree (MST)
    • Kruskal's Minimum Spanning Tree-algoritme
    • Verschil tussen het algoritme van Prim en Kruskal voor MST
    • Toepassingen van het Minimum Spanning Tree-probleem
    • Minimale kosten om alle steden met elkaar te verbinden
    • Totaal aantal overspannende bomen in een grafiek
    • Minimale productomspannende boom
    • Omgekeerd verwijderalgoritme voor minimaal overspannende boom
    • Boruvka's algoritme voor Minimum Spanning Tree

    Topologische sortering:

    • Topologische sortering
    • Alle topologische soorten van een gerichte acyclische grafiek
    • Kahn's algoritme voor topologische sortering
    • Maximale randen die aan DAG kunnen worden toegevoegd, zodat het DAG blijft
    • Langste pad in een gerichte acyclische grafiek
    • Topologisch Soort grafiek met behulp van de vertrektijd van het hoekpunt

    Connectiviteit in grafiek:

    • Articulatiepunten (of snijpunten) in een grafiek
    • Dubbelverbonden componenten
    • Bruggen in een grafiek
    • Euleriaans pad en circuit
    • Fleury's algoritme voor het afdrukken van Euleriaans pad of circuit
    • Sterk verbonden componenten
    • Tel alle mogelijke wandelingen van een bron naar een bestemming met exact k randen
    • Eulercircuit in een gerichte grafiek
    • Lengte van de kortste keten om het doelwoord te bereiken
    • Zoek of een reeks strings aan elkaar kan worden gekoppeld om een ​​cirkel te vormen
    • Het algoritme van Tarjan om sterk verbonden componenten te vinden
    • Paden om door elke knooppunten te reizen met behulp van elke rand (Zeven Bruggen van Königsberg)
    • Dynamische connectiviteit | Set 1 (incrementeel)

    Maximale stroom in grafiek:

    • Introductie van probleem met maximale stroom
    • Ford-Fulkerson-algoritme voor maximaal stroomprobleem
    • Vind het maximale aantal niet-aaneengesloten paden tussen twee hoekpunten
    • Vind de minimale s-t-snede in een stroomnetwerk
    • Maximale bipartiete matching
    • Probleem met kanaaltoewijzing
    • Inleiding tot het Push Relabel-algoritme
    • Karger's algoritme - Set 1 - Introductie en implementatie
    • Dinic's algoritme voor maximale flow

    Sommigen moeten problemen in de grafiek doen:

    • Zoek de lengte van het grootste gebied in de Booleaanse matrix
    • Tel het aantal bomen in een bos
    • Een Peterson-grafiekprobleem
    • Kloon een ongerichte grafiek
    • Grafiekkleuren (inleiding en toepassingen)
    • Implementatie van Travelling Salesman Problem (TSP).
    • Vertex Cover Probleem | Set 1 (inleiding en benaderingsalgoritme)
    • K-centra Probleem | Set 1 (hebzuchtig benaderingsalgoritme)
    • Erdos Renyl-model (voor het genereren van willekeurige grafieken)
    • Chinese postbode of route-inspectie | Set 1 (introductie)
    • Hierholzer's algoritme voor gerichte grafiek
    • Controleer of een bepaalde grafiek bipartiet is of niet
    • Slang- en ladderprobleem
    • Boggle (Vind alle mogelijke woorden in een bord met karakters)
    • Hopcroft Karp-algoritme voor maximale matching-introductie
    • Minimale tijd om alle sinaasappels te laten rotten
    • Construeer een grafiek van gegeven graden van alle hoekpunten
    • Bepaal of er een universele put bestaat in een gerichte graaf
    • Aantal sink-knooppunten in een grafiek
    • Twee kliekjesprobleem (controleer of de grafiek in twee kliekjes kan worden verdeeld)

    Enkele quizzen:

    • Quizzen over het doorlopen van grafieken
    • Quizzen op het kortste pad van de grafiek
    • Quizzen op de grafiek Minimale overspanningsboom
    • Quizzen over grafieken

    Snelle links:

    • Top 10 sollicitatievragen over Depth First Search (DFS)
    • Enkele interessante kortste padvragen
    • Video's over grafieken

    Aanbevolen:

    • Leer datastructuur en algoritmen | DSA-zelfstudie