Graf datastruktur og Algorithms (Eksempel)

Af: Sarah Chen Sarah Chen
Hours Opdateret

⚡ Smart opsummering

Grafdatastruktur er en ikke-lineær samling af hjørner og kanter, hvor hver kant forbinder et par hjørner. Grafer modellerer virkelige netværk såsom kort, sociale forbindelser og websider og understøtter mange kraftfulde algoritmer.

  • 📐 Struktur: En graf G = (V, E) parrer et sæt af hjørner (knuder) med et sæt af kanter (forbindelser) mellem dem.
  • 🔤 Terminologi: Nøglebegreber inkluderer hjørne, kant, grad, ingrad, udgrad, selv-løkke og adjacens.
  • 🗂️ Repræsentation: Grafer gemmes ved hjælp af en adjacensmatrix eller en adjacensliste, hver med forskellige rumlige afvejninger.
  • 🧭 typer: Retningsbaserede, ikke-rettede, vægtede, cykliske, acykliske, komplette, todelte og mere klassificerer grafer efter struktur.
  • 🌐 Applikationer: Google Kortruteføring, sociale netværk, webrangering og ressourceafhængighed er alle afhængige af grafer.
Læs mere

Graf datastruktur og Algorithms

Hvad er en graf i datastruktur?

En graf er en ikke-lineær datastruktur, der består af hjørner og kanter, hvor hjørnerne indeholder informationen eller dataene, og kanterne fungerer som et link mellem et par hjørner.

Det bruges til at løse virkelige problemer, såsom at finde den bedste rute til destinationen og ruten til telekommunikation og sociale netværk. Brugere betragtes som en node i grafen, og ledningerne er de kanter, der forbinder brugerne.

Hvis kanter er repræsenteret som E og hjørner er repræsenteret som V, så kan grafen G skrives som mængden af ​​hjørner og kanter, som f.eks. G (V, E).

Eksempel på graf i datastruktur

Her er et simpelt eksempel på en grafdatastruktur:

Eksempel på graf i datastruktur

Det er en simpel, urettet graf (én slags graf). Her er sættet af hjørner: {A, B, C, D, E, F}. To hjørner skaber en kant. For eksempel er A og B forbundet med en kant. A og F er dog ikke forbundet med nogen kanter.

Grafterminologier i datastruktur

Følgende er nogle vigtige termer, der bruges i grafdatastrukturen:

SemesterBeskrivelse
VertexHvert dataelement kaldes et hjørne eller en node. I billedet ovenfor er A, B, C, D og E hjørnerne.
Kant (bue)Forbindelsesled mellem to knuder eller hjørner kaldes en kant (bue). Den har to ender og er repræsenteret som (startknudepunkt, endingknudepunkt).
Udirigeret kantDet er en tovejs kant.
Instrueret EdgeDet er en ensrettet kant.
Vægtet kantEn fordel med en værdi på.
DegreeI en graf kaldes antallet af kanter forbundet med et hjørne en grad.
IndegreeDet samlede antal indkommende kanter forbundet til et toppunkt.
UdgradeDet samlede antal udgående kanter forbundet til et toppunkt.
SelvløkkeEn kant kaldes en selvløkke, hvis dens to endepunkter falder sammen.
TilknytningHjørner siges at være tilstødende, hvis en kant er forbundet mellem dem.

RELATEREDE ARTIKLER

Typer af grafer i datastruktur

Her er listen over de mest almindelige typer af grafer i datastrukturen:

  • Instrueret graf
  • Udirigeret graf
  • Vægtet graf
  • Tovejs graf
  • Uendelig graf
  • Nul graf
  • Triviel graf
  • Multi graf
  • Komplet graf
  • Forbundet graf
  • Cyklisk graf
  • Instrueret acyklisk graf (DAG)
  • Cyklus graf
  • Bipartitegraf
  • Euler graf
  • Hamilton graf

Hvordan repræsenterer man en graf i en datastruktur?

En graf gemmes normalt i hukommelsen ved hjælp af en af ​​to repræsentationer. Valget påvirker, hvor meget hukommelse grafen bruger, og hvor hurtigt almindelige operationer kører.

  • Nærliggende matrix: Et todimensionelt V × V-array, hvor celle [i][j] er 1 (eller kantvægten), hvis der findes en kant mellem hjørne i og hjørne j, og 0 ellers. Det tillader O(1) kantopslag, men bruger O(V²)-rum, hvilket gør det bedst til tætte grafer.
  • Liste over tilstødende områder: Et array af lister, hvor hvert hjørne gemmer en liste over sine nærliggende hjørner. Det bruger O(V + E)-rum og er effektivt til sparse grafer, hvilket er grunden til, at de fleste grafer i den virkelige verden bruger det.

Du kan læse mere om disse i adjacensliste og matrixrepræsentation af en graf tutorial.

Anvendelser af grafdatastruktur

En graf har mange anvendelsesmuligheder. Der er mange algoritmer, der bruger grafer. Her er nogle af grafens anvendelser:

  • Google Kort bruger grafer til at finde krydset mellem to veje og beregne afstanden mellem to steder. For eksempel, Dijkstra, for at finde den korteste afstand mellem kilde- og destinationsplacering.
  • Facebook bruger grafer til at finde brugernes fælles venner. Dens algoritme betragter hver bruger som en node i en graf.
  • Til ressourceallokering anvendes en DAG (Directed Acyclic Graph). Den kontrollerer ressourcernes afhængighed.
  • Google Søgemaskiner bruger grafer til at lave rangeringen af ​​hjemmesider.
  • Et kortping Enheden bruger grafdatastrukturen.
  • A router og dens protokol bruger grafen til at lære stien til destinationen.

Ofte Stillede Spørgsmål

Grafiske neurale netværk lærer fra grafstrukturerede data til svindeldetektering, anbefalinger og lægemiddelforskning. Vidensgrafer understøtter besvarelse af AI-spørgsmål, og deep learning-rammer modellerer hver beregning som en graf over operationer.

Ja. AI-assistenter som GitHub Copilot kan generere BFS-, DFS-, Dijkstra- og topologiske sorteringsimplementeringer ud fra en almindelig beskrivelse. Du bør stadig teste kanttilfælde såsom frakoblede noder, cyklusser og tomme grafer, før du bruger koden.

Et træ er en særlig type graf, der er forbundet og ikke har nogen cyklusser, med præcis én sti mellem to vilkårlige noder. En graf er mere generel: den kan indeholde cyklusser, usammenhængende dele og rettede eller vægtede kanter.

De to primære traverseringsmetoder er Breadth-First Search (BFS), som udforsker niveau for niveau ved hjælp af en kø, og Depth-First Search (DFS), som udforsker så dybt som muligt ved hjælp af en stak eller rekursion før tilbagesøgning.trackonge.

Opsummer dette indlæg med: