Datastrukturer 101: Grafer - En visuel introduktion til begyndere

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

? Velkommen! Lad os starte med nogle vigtige sammenhænge. Lad mig spørge dig om 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, så har du bestemt brugt grafer, og du vidste det ikke engang! Overrasket? ? Jeg var også! Denne artikel giver dig en visuel introduktion til en verden af ​​grafer, deres formål, elementer og typer.

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

? Virkelige applikationer - Magien begynder!

Grafer bruges i forskellige brancher og områder:

  • GPS-systemer og Google Maps bruger grafer til at finde den korteste vej 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øgeresultaterne.
  • 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 graferat 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:

? Byggesten

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

Lad os se dem mere detaljeret! ?

  • Noder: de 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 til andre lignende elementer i et netværk.
  • Kanter: de er forbindelser mellem knudepunkterne. De kunne repræsentere gader, fly, busruter, en forbindelse mellem to brugere på et socialt netværk eller noget, der muligvis repræsenterer en forbindelse mellem knudepunkterne i den sammenhæng, 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 gå ikke i panik! ? Du kan muligvis stadig gå fra en node til en anden ved at give en sekvens af 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 (højre), kan du gå fra den lilla knude til den orange knude, til den lyserøde knude, til den grønne node og til sidst nå den gule node. ?

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

Ation Notation & terminologi

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

  • |V|= Samlet antal hjørner ( noder ) i grafen.
  • |E|= Samlet antal forbindelser ( kanter ) i grafen.

I eksemplet nedenfor, |V| = 6fordi der er seks noder (cirkler) og

|E| = 7fordi der er syv kanter (linjer).

? Typer af grafer

Grafer klassificeres ud fra egenskaberne ved deres kanter (forbindelser). Lad os se nærmere på dem! ?

1️⃣ Direkte grafer

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

Som du kan se i nedenstående diagram, har kanterne (forbindelser) 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.

? Hvis vi f.eks. Opretter en graf til en pizzaleveringstjeneste, der repræsenterer en by, kan to huse (noder) 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 slet ikke vende tilbage til din oprindelige placering, hvis der ikke er nogen sti med de rigtige retninger. ? I diagrammet nedenfor 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. ”

2️⃣ Ikke-dirigerede grafer

I denne type graf er kanterne ikke-rettet (de har ikke en bestemt retning). Tænk på ikke-rettede kanter som tovejs gader. Du kan gå fra en node 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 ikke er rettet.

? For vores pizzaleveringstjeneste ville dette betyde, at leveringsmotorcyklen 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 retur. ?

? Vægte? - Ja, vægte!

1️⃣ Vægtede grafer

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

Vægte kan f.eks. 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 sammenhæng, du arbejder med.

Disse vægte bruges af Dijkstras 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 Dijkstras algoritme! ?).

2️⃣ Uvægtede grafer

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

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

? 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, hvordan du vil repræsentere denne datastruktur i din kode. Lad os se de forskellige typer! ?

1️⃣ Tætte grafer

Tætte grafer har mange kanter. Men vent! Know️ Jeg ved, hvad du skal tænke, hvordan kan du bestemme, hvad der kvalificerer 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 orienteret graf. Hvis der er |V|noder i en rettet graf (i eksemplet nedenfor, seks noder), betyder det, at hver node kan have op til |v|forbindelser (i eksemplet nedenfor seks forbindelser).

Hvorfor? Fordi hver node muligvis kan 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| , hvilket er det samlede antal noder ganget med det maksimale antal forbindelser, som hver node kan have.

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

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

2️⃣ Sparse grafer

Sparse grafer har få kanter. Som du kan se i diagrammet nedenfor, er der ikke mange forbindelser mellem noderne.

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

️ Mød cykler!

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

Du bemærkede sandsynligvis, 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 node. 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 for "cykler". De er gyldige stier, der starter og slutter ved samme node. For eksempel kan du i diagrammet nedenfor se, at hvis du starter ved en hvilken som helst node, kan du vende tilbage til den samme node ved at følge kanterne.

Cykler er ikke altid "isolerede", 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 node og finde en sti, der fører dig tilbage til den samme node.

? Sammenfattende ...

  • Grafer er fantastiske datastrukturer, som du bruger hver dag via Google Søgning, Google Maps, GPS og sociale medier.
  • De bruges til at repræsentere elementer, der deler forbindelser .
  • Elementerne i grafen kaldes noder, og forbindelserne mellem dem kaldes kanter .
  • Grafer kan dirigeres, når deres kanter har en bestemt retning, svarende til envejsgader, eller ikke-rettet, når deres kanter ikke har en bestemt retning, svarende til tovejsgader.
  • Kanter kan have en værdi tilknyttet, 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 node.

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

Det vigtige er at ikke stoppe spørgsmålstegn. Nysgerrighed har sin egen grund til at eksistere. - Albert Einstein

? tak!

Jeg håber virkelig, at du kunne lide min artikel. ❤️

Følg mig videreTwitter. ?