Datakonstruktioner 101: Grafer - En visuel introduktion til begyndere

Lær de datastrukturer, du bruger hver dag, at kende

Velkommen! Lad os starte med nogle vigtige kontekster.

Lad mig spørge dig noget:
Bruger du Google Søgning?
Bruger du Google Maps?
Bruger du sociale mediesider?

Hvis dit svar er "ja" på et af disse spørgsmål, har du bestemt brugt grafer, og du vidste det ikke engang! Overrasket? Det var jeg også! Denne artikel giver dig en visuel introduktion til grafernes verden, deres formål, elementer og typer.

Disse datastrukturer fandt virkelig min opmærksomhed på grund af deres fantastiske evner. De er så magtfulde, at du ikke engang kan forestille dig, hvor forskellige deres virkelige verdener kan være. Lad os begynde!

Real-World Applications - Magien begynder!

Grafer bruges i forskellige brancher og felter:

  • GPS-systemer og Google Maps bruger grafer til at finde den korteste sti fra en destination til en anden.
  • Sociale netværk bruger grafer til at repræsentere forbindelser mellem brugere.
  • Google-søgealgoritmen bruger grafer til at bestemme relevansen af ​​søgeresultater.
  • Operations Research er et felt, der bruger grafer til at finde den optimale vej til at reducere omkostningerne ved transport og levering af varer og tjenester.
  • Selv kemi bruger grafer til at repræsentere molekyler !!!

Deres applikationer er fantastiske, ikke?
Lad os starte vores rejse gennem denne verden!

Mød grafer!

Nu hvor du har en vis kontekst, lad os starte med at tale om deres hovedformål og elementer.

Grafer bruges til at repræsentere, finde, analysere og optimere forbindelser mellem elementer (huse, lufthavne, placeringer, brugere, artikler osv.).

Dette er et eksempel på, hvordan en graf ser ud:

Kurve.

Byggesten

Jeg er sikker på, at du har bemærket to hovedelementer i diagrammet ovenfor: cirkler og tykke linjer, der forbinder dem. De kaldes henholdsvis knudepunkter og kanter.

Lad os se dem mere detaljeret!

  • Koder: Det er de elementer, der skaber netværket. De kunne repræsentere huse, placeringer, lufthavne, havne, busstoppesteder, bygninger, brugere, dybest set alt hvad du kunne repræsentere som forbundet med andre lignende elementer i et netværk.
  • Kanter: det er forbindelser mellem knudepunkterne. De kunne repræsentere gader, fly, busruter, en forbindelse mellem to brugere i et socialt netværk eller noget, der muligvis kan repræsentere en forbindelse mellem knudepunkterne i den kontekst, du arbejder med.

Hvad sker der, hvis der ikke er nogen forbindelse?

Hvis to noder ikke er forbundet med en kant, betyder det, at der ikke er nogen direkte forbindelse mellem dem. Men panik ikke! Du er muligvis stadig i stand til at gå fra en knude til en anden ved at følge en række kanter, svarende til at køre gennem flere gader for at nå din endelige destination. ️

For eksempel, i diagrammet nedenfor, selvom der ikke er nogen direkte forbindelse (kant) mellem den lilla knude (venstre) og den gule knude (til højre), kan du gå fra den lilla knude til den orange knude, til den lyserøde knude, til den grønne knude og nå til sidst den gule knude.

Ingen direkte forbindelse mellem den lilla og gule knude.

Dette er et vigtigt aspekt af grafer, som du kan søge efter det element, du leder efter, ved at følge de tilgængelige stier.

Notation & terminologi

Det er meget vigtigt at lære det formelle "sprog" at arbejde med grafer:

  • | V | = Samlet antal vertices (noder) i grafen.
  • | E | = Samlet antal forbindelser (kanter) i grafen.

I eksemplet nedenfor viser | V | = 6, fordi der er seks noder (cirkler) og
| E | = 7, fordi der er syv kanter (linjer).

Kurve.

Typer af grafer

Grafer klassificeres ud fra kendetegnene for deres kanter (forbindelser). Lad os se dem i detaljer!

Rettede grafer

I rettede grafer har kanterne en retning. De går fra en knude til en anden, og der er ingen måde at vende tilbage til den indledende knude gennem denne kant.

Som du kan se i nedenstående diagram, har kanterne (forbindelserne) nu pile, der peger på en bestemt retning. Tænk på disse kanter som envejsgader. Du kan gå i en retning og nå din destination, men du kan ikke vende tilbage gennem den samme gade, så du skal finde en alternativ sti.

Retning af graf.

Hvis vi for eksempel opretter en graf til en pizzaleveringstjeneste, der repræsenterer en by, kan to huse (noder) muligvis være forbundet med en envejsgade (kant). Du kunne komme fra hus A til hus B gennem denne gade, men du kunne ikke gå tilbage, så du bliver nødt til at tage en alternativ vej.

Bemærk: I en rettet graf kan du muligvis overhovedet ikke vende tilbage til din oprindelige placering, hvis der ikke er nogen sti med de rette retninger. I nedenstående diagram kan du se, at du med succes kan gå fra den lilla knude til den grønne knude, men bemærk, at der ikke er nogen måde at vende tilbage fra den grønne knude til den lilla knude, fordi kanterne er “envejsgader. ”

Ingen vej tilbage.

Udirigerede grafer

I denne type graf er kantene ikke rettede (de har ikke en bestemt retning). Tænk på rettede kanter som tovejsgader. Du kan gå fra en knude til en anden og vende tilbage gennem den samme "sti".

Bemærk: Når du ser et diagram over en graf, hvor kanterne ikke har pile, der peger i en bestemt retning, kan du antage, at grafen er ret.

For vores pizzaleveringstjeneste vil dette betyde, at leveringscyklen kan gå fra kilden til destinationen gennem den samme gade eller sti (til deres lettelse! ).

I nedenstående graf kan du gå fra den lilla knude til den grønne knude og tilbage gennem den samme sti, så du ikke når et punkt uden tilbagevenden.

Du kan vende tilbage!

Vægte? - Ja, vægte!

Vægtede grafer

I vægtede grafer har hver kant en værdi tilknyttet den (kaldet vægt). Denne værdi bruges til at repræsentere et bestemt kvantificerbart forhold mellem de knudepunkter, de forbinder.

For eksempel kan vægte repræsentere afstand, tid, antallet af forbindelser, der deles mellem to brugere i et socialt netværk, eller noget, der kan bruges til at beskrive forbindelsen mellem noder i den kontekst, du arbejder med.

Vægtet graf.

Disse vægte bruges af Dijkstra's algoritme til at optimere ruter ved at finde de korteste eller billigste stier mellem noder i et netværk. (Hold øje med en artikel om Dijkstra's algoritme! ).

Uvægtede grafer

I modsætning hertil har uvægtede grafer ikke vægte, der er forbundet med deres kanter. Et eksempel på denne type graf findes i sociale netværk, hvor kanterne repræsenterer forbindelsen mellem to brugere. Forbindelsen kan ikke kvantificeres. Derfor har kanten ingen vægt.

Uvægtet graf.

Bemærk: Du har muligvis bemærket, at indtil videre har vores grafer kun en kant, der forbinder hvert par af noder. Det er naturligt at spørge, om der kan være mere end en kant mellem et par knudepunkter. Dette er faktisk muligt med Multigraphs! De kan have flere kanter, der forbinder det samme par noder.

Multigraph.

Antal kanter! - En vigtig faktor

Det er meget vigtigt at vide, om en graf har mange eller få kanter, fordi dette er en afgørende faktor for at beslutte, hvordan du repræsenterer denne datastruktur i din kode. Lad os se de forskellige typer!

Tette grafer

Tette grafer har mange kanter. Men vent! Jeg ved, hvad du skal tænke, hvordan kan du bestemme, hvad der kan betegnes som "mange kanter"? Dette er lidt for subjektivt, ikke? Jeg er enig med dig, så lad os kvantificere det lidt:

Lad os finde det maksimale antal kanter i en rettet graf. Hvis der er | V | noder i en rettet graf (i eksemplet herunder seks noder), det betyder, at hver node kan have op til | v | forbindelser (i eksemplet herunder seks forbindelser).

Hvorfor? Fordi hver knude potentielt kunne oprette forbindelse til alle andre noder og med sig selv (se “loop” nedenfor). Derfor er det maksimale antal kanter, som grafen kan have, | V | * | V | , som er det samlede antal knudepunkter ganget med det maksimale antal forbindelser, som hver knude kan have.

Når antallet af kanter i grafen er tæt på det maksimale antal kanter, er grafen tæt.

Kurve.

Bemærk: “Loops” opstår, når en knude har en kant, der forbinder den til sig selv. Mærkeligt og interessant, ikke?

Sparsomme grafer

Sparsomme grafer har få kanter. Som du kan se i nedenstående diagram, er der ikke mange forbindelser mellem knudepunkterne.

Når antallet af kanter i grafen er markant færre end det maksimale antal kanter, er grafen sparsom.

Sparsom graf.

️ Mød cykler!

Lad os nu se et vigtigt koncept for at forstå grafer, cyklusser.

Du har sandsynligvis bemærket, at hvis du følger en række forbindelser i en graf, kan du muligvis finde en sti, der fører dig tilbage til den samme knude. Dette er som at ”gå i cirkler”, nøjagtigt som om du kørte rundt i din by og du tog en sti, der kunne føre dig tilbage til din oprindelige placering.

I grafer kaldes disse "cirkulære" stier "cykler". Det er gyldige stier, der starter og slutter ved den samme knude. For eksempel i nedenstående diagram kan du se, at hvis du starter ved en hvilken som helst knude, kan du vende tilbage til den samme knude ved at følge kanterne.

Prøvecyklus.

Cykler er ikke altid "isoleret", fordi de kan være en del af en større graf. Du kan registrere dem ved at starte din søgning på en bestemt knude og finde en sti, der fører dig tilbage til den samme knude.

Cyklus i en graf.

Sammendrag ...

  • Grafer er fantastiske datastrukturer, som du bruger hver dag gennem Google Søgning, Google Maps, GPS og sociale medier.
  • De bruges til at repræsentere elementer, der deler forbindelser.
  • Elementerne i grafen kaldes knudepunkter, og forbindelserne mellem dem kaldes kanter.
  • Grafer kan dirigeres, når deres kanter har en bestemt retning, der ligner envejsgader eller er underrettet, når deres kanter ikke har en bestemt retning, svarende til tovejsgader.
  • Kanter kan have en værdi forbundet med dem, kaldet vægt.
  • Hvis en graf har mange kanter, kaldes den en tæt graf. Ellers kaldes det en sparsom graf, hvis den har få kanter.
  • En række forbindelser kan danne en cyklus, hvis de opretter en sti, der giver dig mulighed for at vende tilbage til den samme knude.

Fortsæt med at lære om disse fantastiske datastrukturer! Det vil være helt værd for din fremtid som udvikler. Jeg lærer om datastrukturer lige nu, og jeg finder dem helt fascinerende.

Det vigtigste er at ikke stoppe med at stille spørgsmålstegn. Nysgerrighed har sin egen grund til eksisterende. - Albert Einstein

Tak!

Jeg håber virkelig, at du kunne lide min artikel.
Jeg sætter stor pris på dine klapper og kommentarer.
Følg mig på Medium | Twitter for at finde flere artikler som dette.

Du kan godt lide at læse mine artikler om datastrukturer: