En effektiv programmerer trenger en solid forståelse av datastrukturer og algoritmer. Tekniske intervjuer vil ofte teste dine problemløsnings- og kritisk tenkningsevner.

Grafer er en av de mange viktige datastrukturene i programmering. I de fleste tilfeller er det ikke lett å forstå grafer og løse grafbaserte problemer.

Hva er en graf, og hva trenger du å vite om den?

Hva er en graf?

En graf er en ikke-lineær datastruktur som har noder (eller toppunkter) med kanter som forbinder dem. Alle trær er undertyper av grafer, men ikke alle grafer er trær, og grafen er datastrukturen som trær stammer fra.

Selv om du kan bygge datastrukturer i JavaScript og andre språk, kan du implementere en graf på forskjellige måter. De mest populære tilnærmingene er kantlister, tilknytningslister, og tilstøtende matriser.

De Khan Academy guide til å representere grafer er en flott ressurs for å lære om hvordan du representerer en graf.

Det finnes mange forskjellige typer grafer. Et vanlig skille er mellom regissert og urettet grafer; disse kommer opp mye i kodingsutfordringer og bruk i det virkelige livet.

instagram viewer

Typer grafer

  1. Rettet graf: En graf der alle kanter har en retning, også referert til som digraf.
  2. Urettet graf: En urettet graf er også kjent som en toveis graf. I urettede grafer spiller retningen på kantene ingen rolle, og traversering kan gå i alle retninger.
  3. Vektet graf: En vektet graf er en graf hvis noder og kanter har en tilknyttet verdi. I de fleste tilfeller representerer denne verdien kostnaden ved å utforske den noden eller kanten.
  4. Finitt graf: En graf som har et begrenset antall noder og kanter.
  5. Uendelig graf: En graf som har en uendelig mengde noder og kanter.
  6. Triviell graf: En graf som bare har én node og ingen kant.
  7. Enkel graf: Når bare én kant forbinder hvert par av nodene i en graf, kalles det en enkel graf.
  8. Nullgraf: En nullgraf er en graf som ikke har noen kanter som forbinder nodene.
  9. Multigraf: I en multigraf har minst et par noder mer enn én kant som forbinder dem. I multigrafer er det ingen selvløkker.
  10. Komplett graf: En komplett graf er en graf der hver node kobles til annenhver node i grafen. Det er også kjent som en full graf.
  11. Pseudograf: En graf som har en selvløkke bortsett fra andre grafkanter kalles en pseudograf.
  12. Vanlig graf: En vanlig graf er en graf der alle noder har like grader; dvs. hver node har samme antall naboer.
  13. Tilkoblet graf: En tilkoblet graf er ganske enkelt en hvilken som helst graf der to noder kobles sammen; dvs. en graf med minst én vei mellom hver to noder i grafen.
  14. Frakoblet graf: En frakoblet graf er det direkte motsatte av en tilkoblet graf. I en frakoblet graf er det ingen kanter som forbinder grafens noder, for eksempel i en null kurve.
  15. Syklisk graf: En syklisk graf er en graf som inneholder minst én grafsyklus (en bane som slutter der den startet).
  16. Asyklisk graf: En asyklisk graf er en graf uten sykluser i det hele tatt. Den kan enten være regissert eller uregissert.
  17. Subgraf: En subgraf er en avledet graf. Det er en graf dannet av noder og kanter som er undersett av en annen graf.

EN Løkke i en graf er en kant som starter fra en node og ender på samme node. Derfor, a selvløkke er en løkke over bare én grafnode, som vist i en pseudograf.

Algoritmer for grafgjennomgang

Å være en type ikke-lineær datastruktur, er det ganske vanskelig å krysse en graf. Å krysse en graf betyr å gå gjennom og utforske hver node gitt det er en gyldig bane gjennom kantene. Graftraversalalgoritmer er hovedsakelig av to typer.

  1. Breadth-First Search (BFS): Bredde-først-søk er en grafoverskridende algoritme som besøker en grafnode og utforsker naboene før de går videre til noen av undernodene. Selv om du kan begynne å krysse en graf fra en hvilken som helst valgt node, er den rotnoden er vanligvis det foretrukne utgangspunktet.
  2. Depth-First Search (DFS): Dette er den andre store graftraversalalgoritmen. Den besøker en grafnode og utforsker dens underordnede noder eller grener før den fortsetter til neste node – det vil si å gå dypt først før den går bredt.

Bredde-først-søk er den anbefalte algoritmen for å finne stier mellom to noder så raskt som mulig, spesielt den korteste veien.

Dybde-først-søk anbefales stort sett når du vil besøke hver node i grafen. Begge traversalalgoritmene fungerer bra i alle fall, men den ene kan være enklere og mer optimalisert enn den andre i utvalgte scenarier.

En enkel illustrasjon kan bidra til å forstå begge algoritmene bedre. Tenk på statene i et land som en graf og prøv å sjekke om to stater, X og Y, er tilkoblet. Et dybde-første søk kan gå på en sti nesten rundt i landet uten å være klar over det tidlig nok Y er bare 2 stater unna X.

Fordelen med et bredde-først-søk er at det opprettholder nærhet til gjeldende node så mye som mulig før du går til neste. Den vil finne sammenhengen mellom X og Y på kort tid uten å måtte utforske hele landet.

En annen stor forskjell mellom disse to algoritmene er måten de er implementert i kode. Bredde-først søk er en iterativ algoritme og bruker en kø, mens et dybde-først-søk vanligvis implementeres som en rekursiv algoritme som utnytter stable.

Nedenfor er noen pseudokode som demonstrerer implementeringen av begge algoritmene.

Bredde-først søk

bfs (Graph G, GraphNode rot) {
la q være ny Kø
// merk root som besøkt
 root.visited = ekte


// legg til root i køen
q.enqueue(rot)
samtidig som (q er ikke tømme) {
la gjeldende være q.dequeue() // fjern frontelement i køen
 for (naboer n av strøm i G) {
hvis (n erikke ennå besøkt) {
// legg til i køen - slik at du også kan utforske naboene
q.enqueue(n)
 n.besøkt = ekte
 }
 }
 }
}

Dybde-første søk

dfs (Graph G, GraphNode rot) {
// base case
hvis (roten er null) komme tilbake
// merk root som besøkt
 root.visited = ekte
for (naboer n av rot i G)
hvis (n erikke ennå besøkt)
 dfs (G, n) // rekursivt kall
}

Noen få andre graf-traversal-algoritmer stammer fra bredde-først og dybde-først søk. De mest populære er:

  • Toveis søk: Denne algoritmen er en optimalisert måte å finne den korteste veien mellom to noder. Den bruker to bredde-først-søk som kolliderer hvis det er en sti.
  • Topologisk sortering: Dette brukes i rettet grafer for å sortere nodene i ønsket rekkefølge. Du kan ikke bruke en topologisk sortering på urettede grafer eller grafer med sykluser.
  • Dijkstras algoritme: Dette er også en type BFS. Den brukes også til å finne den korteste veien mellom to noder i en vektet rettet graf, som kan ha sykluser eller ikke.

Vanlige intervjuspørsmål basert på grafer

Grafer er blant de viktigste datastrukturer enhver programmerer bør kjenne til. Det dukker ofte opp spørsmål om dette temaet i tekniske intervjuer, og du kan støte på noen klassiske problemer knyttet til temaet. Disse inkluderer ting som "bydommeren", "antall øyer" og problemer med "reisende selger".

Dette er bare noen av de mange populære grafbaserte intervjuproblemene. Du kan prøve dem ut LeetCode, HackerRank, eller GeeksforGeeks.

Forstå grafdatastrukturer og algoritmer

Grafer er ikke bare nyttige for tekniske intervjuer. De har også brukssaker fra den virkelige verden, for eksempel i nettverk, kart, og flyselskapets systemer for å finne ruter. De brukes også i den underliggende logikken til datasystemer.

Grafer er utmerket for å organisere data og hjelpe oss med å visualisere komplekse problemer. Grafer bør imidlertid bare brukes når det er absolutt nødvendig, for å forhindre plasskompleksitet eller minneproblemer.