Graf datastruktur och Algorithms (Exempel)

Vad är en graf i datastruktur?

En graf är en icke-linjär datastruktur som består av hörn och kanter, där hörn innehåller informationen eller data, och kanterna fungerar som en länk mellan par av hörn.

Det används för att lösa riktiga ordproblem som att hitta den bästa vägen till destinationsplatsen och rutten för telekommunikation och sociala nätverk. Användare anses vara en nod i grafen, och ledningarna är kanterna som förbinder användarna.

Om kanter representeras som E och hörn representeras som V, så kan grafen G skrivas som en uppsättning av hörn och kanter, som t.ex. G (V, E)

Exempel på graf i datastruktur

Här är ett enkelt exempel på grafdatastruktur:

Exempel på graf i datastruktur

Det är en enkel oriktad graf (en sorts graf). Här är uppsättningen av vertex: {A, B, C,D,E,F}. Två hörn skapar en kant. Till exempel är A och B länkade med en kant. A och F är dock inte kopplade till några kanter.

Grafterminologier i datastruktur

Följande är några viktiga termer som används i grafdatastruktur:

Termin Description
Vertex Alla dataelement kallas en vertex eller en nod. I bilden ovan är A, B, C, D & E hörn.
Kant (båge) Förbindande länkar mellan två noder eller hörn kallas kant (Arc). Den har två ändar och representeras som (startingVertex, endingVertex).
Oriktad kant Det är en dubbelriktad kant.
Regisserad Edge Det är en enkelriktad kant.
Viktad kant En kant med värde på sig.
Examen I Graph kallas antalet kanter som är kopplade till en vertex en grad.
Indegree Det totala antalet inkommande kanter kopplade till en vertex.
Utgradig Det totala antalet utgående kanter kopplade till en vertex.
Självslinga En kant kallas en självslinga om dess två ändpunkter sammanfaller.
Närhet Vertices sägs ligga intill om en kant är ansluten.

Typer av grafer i datastruktur

Här är listan över de vanligaste typer av grafer i datastrukturen:

  • Regisserad graf
  • Oriktad graf
  • Viktad graf
  • Dubbelriktad graf
  • Oändlig graf
  • Null graf
  • Trivial graf
  • Multi Graph
  • Komplett graf
  • Ansluten graf
  • Cyklisk graf
  • Regisserad acyklisk graf (DAG)
  • Cykeldiagram
  • Bipartitgraf
  • Euler graf
  • Hamilton graf

Tillämpningar av grafdatastruktur

En graf har många användningsfall. Det finns många algoritmer som använder Graphs mycket. Här är några av grafens tillämpningar:

  • Google Maps använder grafer för att hitta skärningspunkten mellan två vägar och beräkna avståndet mellan två platser.
    Till exempel, Dijkstra, för att hitta det kortaste avståndet mellan källan och destinationsplatsen.
  • Facebook använder Graphs för att hitta användarnas gemensamma vän. Dess algoritm betraktar varje användare som en nod i en graf.
  • För resursallokering används DAG (Direct Acyclic Graph). Den kontrollerar resursernas beroende.
  • Googles sökmotor använder grafer för att skapa rankningen för webbplatser.
  • En kartläggningsenhet använder grafdatastrukturen.
  • router och ts protokoll använder grafen för att lära sig sökvägen till destinationsvägen.