En effektiv programmør har brug for en solid forståelse af datastrukturer og algoritmer. Tekniske interviews vil ofte teste dine problemløsnings- og kritiske tænkningsevner.
Grafer er en af de mange vigtige datastrukturer i programmering. I de fleste tilfælde er det ikke let at forstå grafer og løse grafbaserede problemer.
Hvad er en graf, og hvad skal du vide om den?
Hvad er en graf?
En graf er en ikke-lineær datastruktur, der har noder (eller toppunkter) med kanter, der forbinder dem. Alle træer er undertyper af grafer, men ikke alle grafer er træer, og grafen er den datastruktur, som træer stammer fra.
Selvom du kan opbygge datastrukturer i JavaScript og andre sprog, kan du implementere en graf på forskellige måder. De mest populære tilgange er kantlister, tilgrænsende lister, og tilstødende matricer.
Det Khan Academy guide til at repræsentere grafer er en fantastisk ressource til at lære om, hvordan man repræsenterer en graf.
Der er mange forskellige typer grafer. En fælles forskel er mellem
instrueret og urettet grafer; disse kommer meget op i kodningsudfordringer og brug i det virkelige liv.Typer af grafer
- Instrueret graf: En graf, hvor alle kanter har en retning, også kaldet digraf.
- Urettet graf: En urettet graf er også kendt som en to-vejs graf. I urettede grafer betyder retningen af kanterne ikke noget, og traversering kan gå i alle retninger.
- Vægtet graf: En vægtet graf er en graf, hvis noder og kanter har en tilknyttet værdi. I de fleste tilfælde repræsenterer denne værdi omkostningerne ved at udforske den pågældende node eller kant.
- Endelig graf: En graf, der har et begrænset antal noder og kanter.
- Uendelig graf: En graf, der har en uendelig mængde af noder og kanter.
- Triviel graf: En graf, der kun har én knude og ingen kant.
- Simpel graf: Når kun én kant forbinder hvert par af knudepunkter i en graf, kaldes det en simpel graf.
- Nul graf: En nul-graf er en graf, der ikke har nogen kanter, der forbinder dens noder.
- Multigraf: I en multigraf har mindst et par noder mere end én kant, der forbinder dem. I multigrafer er der ingen selvløkker.
- Komplet graf: En komplet graf er en graf, hvor hver knude forbindes med hver anden knude i grafen. Det er også kendt som en fuld graf.
- Pseudograf: En graf, der har en selvløkke bortset fra andre grafkanter, kaldes en pseudograf.
- Almindelig graf: En almindelig graf er en graf, hvor alle noder har lige store grader; dvs. hver node har det samme antal naboer.
- Forbundet graf: En forbundet graf er simpelthen en hvilken som helst graf, hvori to knudepunkter forbindes; dvs. en graf med mindst én vej mellem hver to knudepunkter i grafen.
- Afbrudt graf: En afbrudt graf er det direkte modsatte af en forbundet graf. I en afbrudt graf er der ingen kanter, der forbinder grafens noder, såsom i en nul kurve.
- Cyklisk graf: En cyklisk graf er en graf, der indeholder mindst én grafcyklus (en sti, der slutter, hvor den startede).
- Acyklisk graf: En acyklisk graf er en graf uden cyklusser overhovedet. Den kan enten være instrueret eller uinstrueret.
- Undergrafik: En undergraf er en afledt graf. Det er en graf, der er dannet af noder og kanter, der er delmængder af en anden graf.
EN sløjfe i en graf er en kant, der starter fra en knude og ender ved den samme knude. Derfor, en selvløkke er en sløjfe over kun én grafknude, som det ses i en pseudograf.
Grafgennemløbsalgoritmer
Da det er en type ikke-lineær datastruktur, er det ret vanskeligt at krydse en graf. At krydse en graf betyder at gå igennem og udforske hver knude, da der er en gyldig sti gennem kanterne. Graftraversalalgoritmer er hovedsageligt af to typer.
- Breadth-First Search (BFS): Bredde-først-søgning er en grafgennemløbsalgoritme, der besøger en grafknude og udforsker dens naboer, før den går videre til nogen af dens underknudepunkter. Selvom du kan begynde at krydse en graf fra en hvilken som helst valgt knude, er den rodknude er normalt det foretrukne udgangspunkt.
- Dybde-første søgning (DFS): Dette er den anden store grafgennemløbsalgoritme. Den besøger en grafknude og udforsker dens underordnede knudepunkter eller grene, før den fortsætter til den næste knude – det vil sige, går dybt først, før den går bred.
Bredde-først-søgning er den anbefalede algoritme til at finde stier mellem to noder så hurtigt som muligt, især den korteste vej.
Dybde-først-søgning anbefales for det meste, når du vil besøge hver eneste knude i grafen. Begge traversalalgoritmer fungerer fint under alle omstændigheder, men den ene kan være enklere og mere optimeret end den anden i udvalgte scenarier.
En simpel illustration kan hjælpe med at forstå begge algoritmer bedre. Tænk på et lands stater som en graf og prøv at kontrollere, om to stater, x og Y, er forbundet. En dybde-første søgning kan gå på en sti næsten rundt i landet uden at opdage det tidligt nok Y er kun 2 stater væk fra x.
Fordelen ved en bredde-først-søgning er, at den bevarer nærhed til den aktuelle node så meget som muligt, før den går til den næste. Det vil finde sammenhængen mellem x og Y på kort tid uden at skulle udforske hele landet.
En anden stor forskel mellem disse to algoritmer er den måde, de er implementeret i kode. Bredde-først søgning er en iterativ algoritme og gør brug af en kø, mens en dybde-først-søgning normalt implementeres som en rekursiv algoritme der udnytter stak.
Nedenfor er noget pseudokode, der demonstrerer implementeringen af begge algoritmer.
Bredde-første søgning
bfs (Graph G, GraphNode root) {
lade q være ny Kø// markér root som besøgt
root.visited = rigtigt// tilføje root til køen
q.enqueue(rod)
mens (q er ikke tom) {
lade nuværende være q.dequeue() // fjern frontelement i køen
for (naboer n af strøm i G) {
hvis (n erikke endnu besøgt) {
// tilføje til køen - så du også kan udforske dens naboer
q.enqueue(n)
n.besøgt = rigtigt
}
}
}
}
Dybde-første søgning
dfs (Graph G, GraphNode root) {
// basiscase
hvis (roden er nul) Vend tilbage// markér root som besøgt
root.visited = rigtigt
for (naboer n af rod i G)
hvis (n erikke endnu besøgt)
dfs (G, n) // rekursivt opkald
}
Et par andre graf-traversal-algoritmer stammer fra bredde-først og dybde-først søgninger. De mest populære er:
- Tovejssøgning: Denne algoritme er en optimeret måde at finde den korteste vej mellem to noder. Den bruger to bredde-først søgninger, der kolliderer, hvis der er en sti.
- Topologisk sortering: Dette bruges i rettede grafer for at sortere noderne i den ønskede rækkefølge. Du kan ikke anvende en topologisk sortering på urettede grafer eller grafer med cyklusser.
- Dijkstras algoritme: Dette er også en type BFS. Det bruges også til at finde den korteste vej mellem to noder i en vægtet rettet graf, som kan have cyklusser eller ej.
Almindelige interviewspørgsmål baseret på grafer
Grafer er blandt de vigtige datastrukturer enhver programmør bør kende. Spørgsmål dukker ofte op om dette emne i tekniske interviews, og du kan støde på nogle klassiske problemer relateret til emnet. Disse omfatter ting som "bydommeren", "antal øer" og problemer med "rejsende sælger".
Dette er blot nogle få af de mange populære grafbaserede interviewproblemer. Du kan prøve dem LeetCode, HackerRank, eller GeeksforGeeks.
Forstå grafdatastrukturer og algoritmer
Grafer er ikke kun nyttige til tekniske interviews. De har også brugssager fra den virkelige verden, såsom i netværk, kort, og flyselskabers systemer til at finde ruter. De bruges også i computersystemernes underliggende logik.
Grafer er fremragende til at organisere data og til at hjælpe os med at visualisere komplekse problemer. Grafer bør dog kun bruges, når det er absolut nødvendigt, for at forhindre pladskompleksitet eller hukommelsesproblemer.