Grafiekgegevensstructuur en Algorithms (Voorbeeld)

Wat is een grafiek in de gegevensstructuur?

Een grafiek is een niet-lineaire gegevensstructuur die bestaat uit hoekpunten en randen, waarbij hoekpunten de informatie of gegevens bevatten, en de randen werken als een link tussen paar hoekpunten.

Het wordt gebruikt om echte woordproblemen op te lossen, zoals het vinden van de beste route naar de bestemmingslocatie en de route voor telecommunicatie en sociale netwerken. Gebruikers worden beschouwd als een knooppunt in de grafiek en de draden zijn de randen die de gebruikers verbinden.

Als randen worden weergegeven als E en hoekpunten worden weergegeven als V, dan kan de grafiek G worden geschreven als de verzameling hoekpunten en randen, zoals G (V, E)

Voorbeeld van grafiek in gegevensstructuur

Hier is een eenvoudig voorbeeld van de structuur van grafiekgegevens:

Voorbeeld van grafiek in gegevensstructuur

Het is een eenvoudige, ongerichte grafiek (één soort grafiek). Hier is de set hoekpunten: {A, B, C,D,E,F}. Twee hoekpunten creëren een rand. A en B zijn bijvoorbeeld verbonden met een rand. A en F zijn echter niet met randen verbonden.

Grafiekterminologieën in de gegevensstructuur

De following zijn enkele belangrijke termen die worden gebruikt in de structuur van grafiekgegevens:

Termijn Omschrijving
Toppunt Alle gegevenselementen worden een hoekpunt of een knooppunt genoemd. In de bovenstaande afbeelding zijn A, B, C, D en E de hoekpunten.
Rand (boog) Verbindingsverbindingen tussen twee knooppunten of hoekpunten worden rand (Arc) genoemd. Het heeft twee uiteinden en wordt weergegeven als (startpuntVertex, eindigendVertex).
Ongerichte rand Het is een bidirectionele rand.
Gerichte rand Het is een unidirectionele rand.
Gewogen rand Een rand met waarde erop.
Mate In Graph wordt het aantal randen dat met een hoekpunt is verbonden een graad genoemd.
Ingraad Het totale aantal inkomende flanken verbonden met een hoekpunt.
Hoger diploma Het totale aantal uitgaande randen dat met een hoekpunt is verbonden.
Zelflus Een rand wordt een zelflus genoemd als de twee eindpunten ervan samenvallen.
nabijheid Er wordt gezegd dat hoekpunten aangrenzend zijn als een rand is verbonden.

Soorten grafieken in de gegevensstructuur

Hier is de lijst met de meest voorkomende soorten grafieken in de datastructuur:

  • Gerichte grafiek
  • Ongerichte grafiek
  • Gewogen grafiek
  • Bidirectionele grafiek
  • Oneindige grafiek
  • Nulgrafiek
  • Triviale grafiek
  • Multigrafiek
  • Volledige grafiek
  • Verbonden grafiek
  • Cyclische grafiek
  • Gerichte Acyclische Grafiek (DAG)
  • Cyclusgrafiek
  • Bipartiete grafiek
  • Euler-grafiek
  • Hamilton-grafiek

Toepassingen van grafiekgegevensstructuur

Een grafiek kent veel gebruiksscenario's. Er zijn veel algorithms die veel gebruik maken van grafieken. Hier zijn enkele toepassingen van de grafiek:

  • Google Maps gebruikt grafieken om het snijpunt van twee wegen te vinden en de afstand tussen twee locaties te berekenen.
    Bijvoorbeeld Dijkstra, voor het vinden van de kortste afstand tussen bron- en bestemmingslocatie.
  • Facebook gebruikt Grafieken om de gemeenschappelijke vriend van de gebruikers te vinden. Het algoritme beschouwt elke gebruiker als een knooppunt van een grafiek.
  • Voor de toewijzing van hulpbronnen wordt DAG (Direct Acyclic Graph) gebruikt. Het controleert de afhankelijkheid van de bronnen.
  • Google Search Engine gebruikt grafieken om de ranking voor websites te bepalen.
  • Een kaartapparaat gebruikt de grafiekgegevensstructuur.
  • router en het protocol van t gebruikt de grafiek om het pad van het bestemmingspad te leren.