Graf datastruktur och Algorithms (Exempel)

By: Sarah Chen Sarah Chen
Hours Uppdaterad

⚡ Smart sammanfattning

Grafdatastruktur är en icke-linjär samling av noder och kanter där varje kant länkar samman ett par noder. Grafer modellerar verkliga nätverk som kartor, sociala kontakter och webbsidor, och stöder många kraftfulla algoritmer.

  • 📐 Strukturera: En graf G = (V, E) parar ihop en uppsättning noder (noder) med en uppsättning kanter (länkar) mellan dem.
  • 🔤 Terminologi: Nyckeltermer inkluderar vertex, kant, grad, ingrad, utgrad, självloop och adjacens.
  • 🗂️ Representation: Grafer lagras med hjälp av en adjacentsmatris eller en adjacentslista, var och en med olika rymdavvägningar.
  • 🧭 typer: Riktade, oriktade, viktade, cykliska, acykliska, fullständiga, tvådelade och fler klassificerar grafer efter struktur.
  • 🌐 Program: Google Kartrutning, sociala nätverk, webbrankning och resursberoende är alla beroende av grafer.
Läs mer

Graf datastruktur och Algorithms

Vad är en graf i datastruktur?

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

Det används för att lösa verkliga problem, som att hitta den bästa vägen till destinationen och vägen för telekommunikation och sociala nätverk. Användare betraktas som 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å en grafdatastruktur:

Exempel på graf i datastruktur

Det är en enkel oriktad graf (en typ av graf). Här är mängden av noder: {A, B, C, D, E, F}. Två noder skapar en kant. Till exempel är A och B länkade med en kant. Däremot är A och F inte länkade med några kanter.

Grafterminologier i datastruktur

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

TerminBESKRIVNING
VertexVarje dataelement kallas en nod eller en nod. I bilden ovan är A, B, C, D och E noderna.
Kant (båge)Förbindande länkar mellan två noder eller noder kallas en kant (Arc). Den har två ändar och representeras som (startingVertex, endingVertex).
Oriktad kantDet är en dubbelriktad kant.
Regisserad EdgeDet är en enkelriktad kant.
Viktad kantEn fördel med ett värde på sig.
ExamenI en graf kallas antalet kanter som är förbundna med ett hörn för en grad.
IndegreeDet totala antalet inkommande kanter kopplade till en vertex.
UtgradigDet totala antalet utgående kanter kopplade till en vertex.
SjälvslingaEn kant kallas en självslinga om dess två ändpunkter sammanfaller.
NärhetNomter sägs vara intilliggande om en kant är förbunden mellan dem.

RELATERADE ARTIKLAR

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

Hur representerar man en graf i en datastruktur?

En graf lagras vanligtvis i minnet med hjälp av en av två representationer. Valet påverkar hur mycket minne grafen använder och hur snabbt vanliga operationer körs.

  • Närhetsmatris: En tvådimensionell V × V-matris där cell [i][j] är 1 (eller kantvikten) om en kant finns mellan hörn i och hörn j, och 0 annars. Den tillåter O(1) kantsökning men använder O(V²)-utrymme, vilket gör den bäst för täta grafer.
  • Angränsande lista: En array av listor där varje nodpunkt lagrar en lista över sina angränsande noder. Den använder O(V + E)-utrymme och är effektiv för glesa grafer, vilket är anledningen till att de flesta verkliga grafer använder den.

Du kan läsa mer om dessa i adjacenslista och matrisrepresentation av en graf handledning.

Tillämpningar av grafdatastruktur

En graf har många användningsområden. Det finns många algoritmer som använder grafer. Här är några av grafens tillämpningar:

  • Google Maps använder grafer för att hitta korsningen 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 grafer för att hitta användarnas gemensamma vänner. Dess algoritm betraktar varje användare som en nod i en graf.
  • För resursallokering används en DAG (Directed Acyclic Graph). Den kontrollerar resursernas beroende.
  • Ocuco-landskapet Google Sökmotorer använder grafer för att skapa rankningen för webbplatser.
  • En kartaping Enheten använder grafdatastrukturen.
  • A router och dess protokoll använder grafen för att lära sig vägen till destinationen.

Vanliga frågor

Grafiska neurala nätverk lär sig från grafstrukturerad data för bedrägeriupptäckt, rekommendationer och läkemedelsutveckling. Kunskapsgrafer stöder AI-frågor och djupinlärningsramverk modellerar varje beräkning som en graf över operationer.

Ja. AI-assistenter som GitHub Copilot kan generera BFS-, DFS-, Dijkstra- och topologiska sorteringsimplementeringar från en enkel beskrivning. Du bör fortfarande testa kantfall som frånkopplade noder, cykler och tomma grafer innan du använder koden.

Ett träd är en speciell typ av graf som är sammanhängande och saknar cykler, med exakt en väg mellan två noder. En graf är mer generell: den kan innehålla cykler, frånskilda delar och riktade eller viktade kanter.

De två huvudsakliga traverseringsmetoderna är Breadth-First Search (BFS), som utforskar nivå för nivå med hjälp av en kö, och Depth-First Search (DFS), som utforskar så djupt som möjligt med hjälp av en stack eller rekursion innan bakåtgående sökning.trackung.

Sammanfatta detta inlägg med: